I switched to Posteo [1] and am very happy with them. 1€ per month, based in Germany (but you can choose from many country TLDs [2]) and they take privacy very serious.
I've been a Posteo user for over 7 years now and I couldn't be happier. I also use it for calendar and contacts sync.
It just works. But I doubt it is a Gmail replacement. It is a great email service provider though.