After reading this article , I decided to give the Gmail mobile client a try. Seriously, there are not many bits of software I would install on my phone but since this is from Google, and Gmail is so amazing, I just had to give it a try, and... it doesn't disappoint. This is a seriously cool little application.
I am running it on my Sony Ericsson W810i (which is a phone that you should check out if you are in the market, BTW) and it's fast and has some great features like shortcuts for search and compose. It also seems incredibly fast. I am guessing they download a bunch of stuff at once, although it doesn't seem to take very long to connect. No doubt that usual mail clients on phones don't optimize for packet size so you get lots of little chucky mostly empty packets.
Anyway, it was painless and easy and worked right away. I will let you know if I still like it in a few weeks.