Remember how we used Outlook before GMail because it was the only kid on the block? That's where we are at with GMail. The new mail experience hasn't been built yet.
Fastmail isn't free, but it has everything which made Gmail good in the first place. And since you're paying, you know email is the product and that you won't become collateral in a user-hostile Google+ like strategy.
For those interested in checking it out, feel free to use to use the following referral link while doing so.
At the very least Fastmail is terribly fast :), which you immediately see when you're using their web interface. They keep hot and recent data on SSDs.
Also, since they actually implement IMAP correctly (they are one of the major contributors of the open source Cyrus IMAP server), things like MailTags work[1], whereas they don't on Google Mail.
The only thing that is missing are push notifications (e.g. via ActiveSync), but they are working on an app. In the meanwhile, using pushover is also an option.
They actually have a two month trial, so they're definitely worth trying out.
I moved from Gmail to Fastmail last month, and man is it nice. The import process smoothly pulled over 30K messages and folders over IMAP in a few hours. As an IMAP server behind iOS and Apple Mail, no problems at all, and their webmail UI is hands down the fastest cleanest Web app I've ever seen. Just stellar so far.
Many people used Hotmail (originally Hotmail) but many people also used Yahoo Mail (originally Rocketmail), which was generally as good or better.
Unfortunately for those people (eg me), Yahoo Mail is now unusably horrible while the new "Hotmail" is generally as good as Gmail and sometimes better. (The web interface is slower, but if you're concerned about speed then you're not using the web interface.)
For those interested in checking it out, feel free to use to use the following referral link while doing so.
http://www.fastmail.fm/?STKI=11413330
Obvious disclaimer: The link above is a referral link. I will benefit if you use it.