For Windows Mobile, I use:
Opera 9.7 beta mostly, the latest builds can be found
here.
Iris Browser for Gmail - this allows you to use the iPhone version of Gmail. Opera technically will run it too, but gets some errors. They got bought out by RIM though, so 1.1.9 will be the last one. Hopefully Google allows us to use the better version of their Gmail soon before Iris stops working. You can get it
here still.
Very rarely will you need to see a full "dekstop" version of a site, but when you do you can use Skyfire. The interface is terrible, it's slow as shit, and a resource hog.
If you get an Android, you only have one choice anyway I think. It also gets the "good" version of Gmail though, so it might be all you need.