My wife got me an iPhone for my birthday. I don't think I really appreciated how incredibly awesome it was until now. I'm a Gmail user and for a day or two I was having issues with using it on the phone because it would try to download thousands of archived messages and cc myself creating lots of duplicates. But after deleting the account setup on the phone, setting Gmail to only allow emails from today on be available through POP, and turning off 'Recent mode' things are working out pretty well. I have it setup so that whenever I check my email on the phone Gmail archives the messages so that they don't show up in the inbox. Then, I can either reply to them on the phone or if I want to process them on a computer I can just go get the archived message. Emails sent from the phone magically show up as sent from my Gmail account, so everything's gravy.
Update: Nope, the mail app on the iPhone is horrible. It loves to grab messages that I've archived. m.gmail.com is the way to go.