I heartily recommend FastMail. I've been using them for a couple years now for all my mail, and they've been great.
They have so many features it's almost comical (it's all in the small details, e.g., you can download your list of last login times as a CSV file; they can SMS you a one-time password if you're in an Internet cafe; etc.).
Once I had a problem with incoming mail from a certain domain not reaching my inbox, and they were extremely helpful. it felt like the guy had nothing else to do but help me. (Oh, and it turned out the problem was on another network, not their end).
In two years I've never experienced any outage.
Really, overall an awesome service (they're not paying me to write this, promise!)