I'm also in the process of leaving Gandi and I've written a post about it here.
If you're ok with leaving your domains and nameservers at Gandi you just need to edit your DNS records and point them to another email service.
Migadu and MXroute work like you described, one account, multiple domains and mailboxes, they charge for what you use (mails and storage) not mailboxes. They will give you the DNS records to add to your nameservers.
You can use imapsync to copy your mail over to the new mailbox.
Check what it will cost to renew your domains, I had a surprise there too.
You can also transfer domains to another registrar, which may offer a free mailbox with it like Gandi used to do.
There are also other options, like using external nameservers. You can do any combo of domain registrar, DNS service and email service you want, ranging from having them all at one provider to using a different provider for each.