Postbox
http://www.postbox-inc.com/ has really good gmail integration, supports labels properly and can use gmail keyboard shortcuts. Sparrow used to be what I recommend, and it's what I still use for now just because I'm used to it, but it's no longer in active development so it's not really worth paying for it now.
Milt