I'd avoid Tuta. Suspended an acct for inactivity and then when I went to replace it (with diff IP and name, no less) I got "flagged for review, cannot send/receive" then they said "send us a message with this address that can't send supposedly," and I gave up on them.

I've seen a lot of people recommend Posteo but I whould not use them. Because they haven't enabled DMARC. https://mxtoolbox.com/SuperTool.aspx?action=dmarc%3Aposteo.de&run=toolpage

All major email providers have enabled DMARC. Gmail https://mxtoolbox.com/SuperTool.aspx?action=gmail.com&run=toolpage

Tuta https://mxtoolbox.com/SuperTool.aspx?action=tuta.com&run=toolpage

I'd recommend Tutanota, ProtonMail, or Mailbox.

I'm using Proton Mail and use an alias to sign up for each service. Works well and if you start getting spam you can pinpoint who leaked your data due to to the unique aliases.

Proton gives me some no good vibe I cannot explain, but it works really good and they really have the human capital to make it work. They do have policies of no-refund that makes that bad sentiment grow. Why no refunding non-used portion or even with a penalty? Regarding its founder, Andy, he did made 3 statements that appeared to support Trump, but I think they were misinterpreted; Andy criticized more the Democrats unrelenting support for the Tech Giants than praising the Republican administration since, with Trump, was the only voice that appeared that was going to favor more the small business vs the mega corporations. Of course, that was the promise that Trump, as with all others he made, were a complete lie. I don't recall any other statements beyond that topic of small business vs big tech.

Mailbox, has been static for a while, but they do offer good service and now they are attempting to modernize. No full privacy by default, but okay for most. Still a bit German-centric. I would recommend this easily.

Posteo would have been my first choice since 5 years ago, but the lack of no being able to use your domain, sorry to say it is inexcusable. They say because your own domain brings some privacy up to light, very true! So advise it, "look, we suggest to use our domains for better privacy for you, but if you want the freedom to move to another provider in the future at the cost of a bit of privacy, you are welcome to bring your own domain". I want to believe the decision was genuinely because they think it is for better privacy and not to create a lock-in for its customers.

Tuta... oh Tuta. I like the people, I believe and trust them the most! Yet, they probably still need to grow a bit so they can have the resources to do better. Their android client does not share data with Google for the push notifications (hello Proton?!). For just email, it is fantastic and for privacy it is the best, period... if you are OK with the lack of support on IMAP and POP3 protocols that is; They should do some bridge like Proton does and I would put in top among all.

On the concerns of the change of political colors in Germany, first regarding privacy, you are more at the wimps of the people of the provider than the leader of the time. I don't really see any country as safe today, not a single one! Now, a right owner like Lavabit's that choose to close shop than given the SSL keys to the US authorities, that is why trust is so critical; I would rather use a provider based in the US with the right owner, than one in Switzerland with one I don't know much about. Once said that, unless you are a high targeted individual, maybe you should not only focus on privacy, besides, sometimes, the best defense is to blend among the no-so-top-notch-privacy providers. In any case, I trust the most Posteo and Tuta, but recommend Mailbox and Proton to most people. I think there is room for a new player here that covers all the shortcomings, but not here yet.

I use Posteo, honestly I don't think it matters much what you choose, anything will be better than Google, encryption is nice but only works if both people have it. Your emails will be as secure as the other address.

Posteo markets itself on being green, if that's important to you.

Proton's founder publicly praised Trump on Twitter, so it's a no-go for me.

I've been using Mailbox for a while and i like it. There are some small annoyances with their web interface but it's not a big problem, I usually use Thunderbird anyway. Mailbox supports IMAP.

Also, you get custom domains.

The government isn't the only threat e2ee protects against. When a non-e2ee service is hacked, the data is free for the taking, if the service is e2ee the data is only available from that moment forward. I'm not going to speak for which provider you should use, but you should reconsider needing e2ee.