This isn't too bad. Get yourself a good imap client (I use Thunderbird, but many will do). Copy all email into local folders.

Migrate your hosting to a new provider. Then you can just as easily push your locally copied messages up.

There are also specific email backup / migration tools, but TBH, I've never really seen the need.

I run coredns.io these days. Simple, many plug-ins available, can handle split brain, etc.

(Personally I just make a change in git and it auto updates my dns boxes)