Prepárate para los mensajes privados!!
Antes de comunicar a tu actual proveedor que vas a hacer el cambio sacaría una copia de TODO lo que tengas en ese servidor.
Después has de trabajar como de un cambio normal se tratase.
Subes la web, creas las cuentas de correo, bases de datos, cambio DNS y cancelar antigua cuenta.
Si la cuenta del primer proveedor no te la cancelan estará todo online y tus clientes no deben de darse cuenta del cambio. Además ahora los DNS se propagan en un rato, así que tampoco habrá pérdidas de email en el anterior proveedor.