This will vary by the new email host. But in most scenarios the only downtime will be when the domain is updated to point to the new server. Any changes to the domain can take up to a few hours to fully take effect. Barring that, it’s possible to synchronize two mail accounts so no mail will be lost during the transition. But again, this will vary based on the new email host.