Assuming you want both a web ui, as well as the option to run your own client, SMTP relay, etc:

Yandex Email for Domains (free): https://domain.yandex.com/domains_add/

Zoho Mail (free and paid plans) https://www.zoho.com/mail/zohomail-pricing.html

Exchange Online ($4/user/month) https://products.office.com/en-us/exchange/exchange-online

As for "valuing user privacy/security", that's pretty hard to gauge. Depends on the context I suppose. Yandex seems unlikely to care about an FBI warrant :)

Rackspace Mail is the leader in this category, with 3 million paid mailboxes. They offer webmail/IMAP/POP/Mobile/Exchange hosting, a 100% availability SLA, and 24x7x365 live chat/phone/email support.

Pricing starts at $2/mailbox/month, but there's a $10/month billing minimum. $10/month is more than reasonable for a small business to spend on e-mail hosting, IMO.

https://www.rackspace.com/email-hosting

I run my own mailserver on a $5 debian Digital Ocean node. The only problem I have run into is that DO blocks outgoing SMTP on IPv6, and in spite of complaints it doesn't seem like they intend to ever change that. (You can easily mitigate this by disabling IPv6. But I want to use IPv6, so I'm in the process of switching over to Ramnode.)

If you also want to run a ZNC host or personal webserver, it's a pretty good deal.

Your concerns about self-hosting are fair, but I would encourage you to take a leap of faith and do it anyway. Exim doesn't require any maintenance-- if you get it setup right in the beginning, you'll never have to touch it again.

Running your own mail server certainly has advantages. But, it is typically more than just Exim. You'll need to install something for IMAP access. Or, if you want web mail, something for that. And, even if not right away, eventually, something to deal with spam...it will come soon enough. Also, those pieces tend to require other pieces (backing database engines, etc).

Similarly, you have to read up on things like domainkeys, spf, IPV6, MX records, PTR records, firewalls, etc...then implement them.

I've recently started using http://mailbox.org.

It's hosted in Germany by what seems to be a reasonably serious company, and running https://www.open-xchange.com/ for the web UI (mail, calendar, basic docs).

I have been using Zoho Mail for years without much issue. They do have occasional outages, which can be frustrating, but they're generally alright for what I'm doing.

Fastmail too as many has pointed out, pretty quick response for help issues.

A little plus point, paid more in advance to get the discount.

I'm a happy user.