Buying your own domain.
You can then use whatever provider, or host your email service... but at least you don't need to change addresses when switching anymore.
I would recommend to buy your own domain in case you need to change again. That way, you're not trapped by your email provider and you can change in case you're not satisfied anymore
disroot and autistici have been providing decentralised communication services (like email) free of cost for many years. They are both run by activists and survive on donations, and they don't spy on you or get any money from your data. Also they run freedom-respecting software, so all their code is publicly auditable.
I'm using Infomaniak Mail and am fairly happy so far. They are based in Switzerland and I get custom domain + 5 user accounts for 1.50 EUR/month. I've tried other providers but coming from Gmail I like that their webmail displays email conversation like Google does whereas most other providers just run rainloop or roundcube where threading support isn't quite the same.
Their android app is open source too and can be installed from fdroid. It can be a bit sluggish sometimes though, but K9mail/Thunderbird works fine too.
Cheaper (€30/yr vs ~€50/yr; if you don't need custom domains, €1/mo)
More aliases (25 on mailbox, 50 on own domain. Proton has 10 TOTAL - why custom domain aliases are counted against Proton ones does not make sense to me.)
Support for any number of custom domains AFAICT (Proton Plus supports only one)
Trial account is not allowed to send emails, so fewer issues with services blacklisting proton.me and protonmail.com for spam (hasn't happened to me, but I have heard of some cases)
Can use a regular email client (security tradeoff for E2EE messages - but there already were plenty of discussions on whether E2EE has benefits, especially sending mail to other services)
Perhaps an indirect answer, but I'm using a duck.com forwarder whenever i need to give any address, these days. On top of tracker filtering and random alias generator, once i change addresses I'll only have to update the forwarders destination.
I've been using mailbox.org, and it's pretty great. It's cheap, it's private, and it works well.
I like the idea of e2ee email, but the way they all work it's pretty much a completely useless feature for most people, myself included, and I also like using Thunderbird. It's just not worth the trade off for something I'd basically never get any use out of anyway.
Another one for Tuta, with addy.io as a proxy service. Nice integration with Bitwarden for making new accounts + it's simple to make rules based on the to address for easy filtering.
If you really wanna get started with your own domain I highly recommend just getting https://purelymail.com/ setup for the hosting provider. It's going to be way cheaper than just about anything and you pay for what you use. I've been on it for a few years and never had a problem.
I'm actually busy setting up my own mail server. On my own infrastructure, using public static IPs etc. I'm done with all these other mail providers. I'm going back to the start.
I've been moving over to Fastmail. Easy to use, tons of features, great price. 👍
Also quick tip regardless of which provider you end up on: Register a domain name for yourself and use it for your email address. This way if you want to change email providers again in the future or even host it yourself, you can take your domain name and addresses with you.
My problem is the whole change of address thing. Unfortunately google had perfect timing when they offered a decent amount of storage. It was early enough that changing email was no big deal and late enough that soon it would be. I very much don't like this because if google like just went dark all of a sudden it would be a bad day. Yeah I know its unlikely to the xtreme but still. I know privacy people do not like this idea but I really would like the government to run an email where all citizens are guaranteed one. To me this would make it much easier to have an official one and other emails. I don't get why folks are ok with corporations doing it and trust that they will use safeguards but don't trust the government would. The US postal service is a good example. Laws were well made to protect mail to the point where one way of safeguarding things from police searches was to put it in a stamped envelope. Man I wish our current society and government would be doing things like that again.