Email was designed for people to store their own email on their own device. Webmail changed habits and perception, but it's still possible to store email on your device(s) via IMAP etc. If you use a traditional fat client, you won't "lose" anything switching providers. However, responsibility for backups and disaster recovery falls (back) on your shoulders. This is the trade-off that keeps people on webmail, IMHO, even more than having to deal with blacklists, etc.

It should be possible to download all mails via IMAP and upload them again (also via IMAP) to the new mail service server.

Then you can even continue to use the new mail providers webmail, you only need to use an IMAP client once! :)

That's, what imapsync is for:

https://imapsync.lamiral.info/

Use a provider that offers POP3 and download everything. This is what I do. My archive goes back to the last millennium.

How on earth does this get a downvote? Valid advice and on topic.

Not if you use a real email client

No.