I moved host twice in my on-line lifetime.
The first time was a disaster, but taught me a lot about the process!
The second time was, by contrast, a much smoother process.
The painless way seems to be to find a new host and set up a dummy domain there to get everything working.
Next, you have to go through the process of migrating your domain. Your new host should have full instructions on how to do this. There are restrictions - the transfer may not be immediately possible if you are close to the domain renewal date, for example. Some security measure to prevent the domain being hijacked, I think.
As soon as the transfer is complete, you can upload your website content and set up your mail boxes. There may be a period when your site and email are unavailable as it can take time for the new domain registration to be recognised across the Internet, but I did not find this to be an issue.
As a backup I use ContactOffice - a wonderful tool that allows me to manage multiple email accounts from a single login (and also manages to cicrcumvent webmail blocking that some companies implement.) There are various plans, including a free account, and you get another email address that can be your backup.