I think the best suggestions I’ve seen from other web sites are:
Brendan Fraser as Carrot. It’ll never happen, but he’s got that goofy, boyish earnest thing going on, besides being very tall and imposing without being brutish.
Michael Hogan as Vimes. My only gripe would be that I think he’s a little too old, but if Saul Tigh was any indication, the man can do complex, layered, surly-with-a-good-heart like nobody’s business.
I also really liked Jeremy Irons as Vetinari. The voice alone is excellent; it’s just so silky smooth and seductive, yet he can make it sharp and dangerous in an instant when he needs to.
Angua’s tough. Seems to me she needs to be long and lean and fit, with an undercurrent of danger, yet still feminine. Lena Heady, maybe?
Nick Frost as Colon?