I've been using Fastmail.com since December, 2014 now and I'm still very happy with them. I use them with a few of my own domains and I've never had any issue sending or receiving any email. Recently, they even got a 1Password integration that allows you to directly create a masked email for a service from my 1Password UI. Search works perfectly, labels feel good to use and the filters are very flexible. If the UI doesn't allow you what to do, you could even directly write your own Sieve scripts.

First, I believe you're making the wrong assumption that a good replacement is web-based. The web is a poor mechanism interface for accessing email. Use a mail client! That will work on PCs, laptops and mobile apps - and you don't depend on your email provider for your usage experience; they all offer IMAP (and many offer POP3). That means you'll have search, labels, elaborate automated filters - including custom actions on your computer, which no web-based interface will offer you (I think). Most email providers do offer a web interface, and some of those are pretty nice, but I'd always consider them a fallback.

Anyway, among the popular providers, I am partial to ProtonMail:

https://en.wikipedia.org/wiki/Proton_Mail

it's Swiss, run by a non-profit, and originally crowd-funded. Over 100 Million users, IIANM. I am not a cyber-security expert, so I can't claim to have audited them for security or privacy bona fides (but maybe somebody has?).

I've also heard suggestions to try Tuta (tuta-nota), but have never tried it myself.

There are also many smaller providers. Specifically, many Internet access providers also provider email services. Not that they are super trustworthy, but - there's a good chance you're not just hading everything over to one of the behemoths like Google or Microsoft.

If you do end up on one of the bigger providers - it's probably best to be on one that's not linked to the government where you live. So if you're in a NATO country you could go for yandex or mail.ru and if in Russia then maybe GMX?

Unfortunately - wherever you take your email - when you write a GMail address, Alphabet has a hold of your correspondence again. So, we need to convince our friends to ditch Google as well.

I've been using AWS WorkMail since it was released. I prefer this arrangement because I can administer the related domain & DNS concerns in the same place.

$4/m seems nominal for a 50GB mailbox with no weird adtech shit built in.