There are few things you can consider:
1) Moving hosting completely to the new provider. Good place to start: https://webhostinggeeks.com/besthosting.html
2) Stay with the current hosting provider and use 3rd party email service to manage your email by forwarding MX record to the new provider like Gmail. You can use Gmail to handle all you email for you business (free unto 10 email addresses). Your email will be with your own domain name. Here's more info in Gmail for Businesses: http://www.google.com/enterprise/apps/business/products.html
3) Keep domain with current hosting provider and point a-record to the new provider if transferring domain is problematic. This is very typical with Godaddy, their hosting service is a huge problem - a lot of complaints, but domains management is great. So you just have all your domains with them and point the DNS record to the new hosting provider (you need dedicated IP for your hosting account though and shared hosting providers don't offer that too often).
The 3rd option is a bit complex, I would suggest to pick one of the first 2.