I switched to Fastmail about 2 weeks ago and their POP retrieval feature made it really easy to get all emails from from my old account. I just updated my email address with a service when first using it after making the switch. And I reply to emails from my new address.

I was looking into ProtonMail and Riseup as well. There are lots of good alternatives to Gmail.