You can really make your life easier by not using Gmail for starters.
Fastmail.fm is $40/year to use with your own domain.
Rackspace can be had for as little as $2/mo (you have to purchase 5 IMAP accounts for $10/mo, then contact their support to have it knocked down to only 1 IMAP account for $2/mo)
Then you can use any email client you want without having to use something specific to Google.
I personally use Postbox, but I can just as easily use Thunderbird or Mail.app.
I refuse to give Google access to my email for advertising. Scummy company, but if you choose to go the Google route your options are going to be more limited for a reliable email client.
Yes, Gmail is accessible via IMAP, but it changes certain key things about organization and deleting that drive me bonkers, personally.
Also, believe it or not, Entourage in the latest Office is actually a really good email client too.