GMail ... Excellent!
My first read on the interface is that I absolutely love the threading and labeling features. I knew GMail would be a fit after I heard the system described because I am a fanatic user of search folders in Outlook 2003, so a mail system powered by the finest search engine in the world was a sure thing.
If you haven't checked out Marcie's blog, you really should.