They all suck from experience in vastly different ways. I'd do one of the following:

1. Use webfaction's shared email service at http://webfaction.com and stick to IMAP. This is an old fashioned shared hosting system.

2. Use digital ocean or linode and build your own mail server.

I do #2 and have four domains and am happy with it. I don't have contact and calendar sync - that's the only problem but this doesn't really bother me. There are hundreds of open source CalDAV and CardDAV solutions available though for all platforms.

With these solutions you are free from the chains of a single vendor as they are easy to move and won't have to worry about getting shafted by Google/Microsoft etc. Three of the four domains I host are refugees from the recent live domains being shut down fiasco.

Or you could pay for Google apps and cross your fingers every day that they don't deprecate something you need.