[fencepost]

I see a bunch of options, and a few people complaining for many that they're too expensive.

I wish I could bold this, but:

For a paid mailbox on professionally-managed systems that are likely to be able to stay around, expect to pay around $5/month probably annualized.

Fastmail Pro? $5. Office 365 Business Basic (Exchange/OneDrive)? $5. KolabNow? $4.50-5. Protonmail? €5-8. Heck, GSuite? Starts at $5. Most of the other paid options in here? Almost certainly in that same range, or there are noticeable drawbacks (e.g. no custom domains on Posteo). Hosting your own on a Digital Ocean droplet or other comparable small VM? Probably going to average out to around the same, plus your time administering.

It's probably possible to do this for less, particularly if you consider your time spent on dealing with any issues to be free of cost. For the rest of us, it seems that $5/month plus or minus a dollar or so is likely the consensus price out there and nobody's really managed to compete for less than that.

GMail does it free because for the vast majority of users people stay signed in so Google has a verified signed in user for ad targeting across Google's properties including their ad networks, and this likely includes on Android if someone clicks a link from the GMail app and opens in the default browser - boom, cookies set and linked to that identity.