You might consider using Google Takeout to export the emails to an mbox file, and then importing that into your new mail server.

When I did it, I did it manually with thunderbird, which is a great way to delete clutter meanwhile

Just select 1000 emails at a time and drop them in another IMAP server folder

Imapsync works well, have uses it hundreds of times on massive accounts. Not with Gmail specifically though. I'd imagine you would lose labels.

IMAPSync is a great tool! It works perfect when migrate mails from one provider to another. In fact, some providers suggest users use this tool rather than implement migration feature by themselves. e.g. Migadu.

GYB is very powerful and flexible, and I've used it to manipulate Gmail accounts in the hundreds of gigabytes.

The community is decently supportive, but of course it is a command line tool so some familiarity with the shell is useful.

https://github.com/GAM-team/got-your-back

Bitten is my tool of choice.

I use infomaniak email with a custom domain. Is around 2 USD per user with unlimited storage. The web UI has an email import tool that works with Gmail. You get a manager UI to manage accounts and settings (sometimes a bit confusing, but works).

After checking many providers, this was the best alternative for me. I hope that helps.

Use skykick its like 12 bucks per mailbox. They have live support so they will even help you setup the migration.