Tim's review of email clients is right on from my point of view, with one small exception: Spotlight search has been working great for me.
I just switched back to the Mac Mail app from Thunderbird due to the lack of decent search, slow response on a number of functions, and lack of Emacs key bindings (I spent an hour hacking around and have some working, but couldn't get most of the esc/alt keystrokes to work correctly.
On the gmail front, I haven't switched over yet, but have been evaluating. I wish it had the AJAX features of the new Yahoo! mail beta, but I imagine that will come.