I second Fastmail.fm

One nice thing is that they are very open about outages, what caused them, and what they'll do to improve things.