The best way to ensure there's no problem (minimal downtime) is to get your hosting and email set up in the new location. Get a copy of your website there and verify it's running ok then set up your email boxes at the new location.
Once that's all done, have the current host point DNS for both WWW and Mail to the new location (you'll need the IP of your new web space).
Wait a day or so to let the routers catch up then check the new website. Verify you're looking at the new website by using tracert or ping from the command line. They will return the final IP address for the DN (www.yourdomain.com). It should match the IP of the new location. Verify your email after the change has propogated. Make sure the new host is ready to handle DNS for your Domain.
Resolve any issues with the new hosting setup now. If the problem will take few days, have the current host switch the DNS back to them.
Once the new location is working correctly, web & email, wait a few more days and then submit the modification request for your DN record so it points to the new NameServers (the NameServers of the new host). This change will take a few days to be accepted and then to propogate through the Inet. Once the mod goes through and the DN record shows the new location wait another week and then you can safely cancel your account with the old host.
The reason for changing where DNS points to is that DNS changes take only a minimal amount of time and while you're waiting the current site is still live. Once it changes the new site is already there and ready to go. If a problem arises, you switch DNS back to the old site and your downtime is kept to a minimum.
This same logic applies to when you make the DN modification. Both locations have DNS set up so that while you're waiting for the DN mod to go through, the old host is still handling DNS but as soon as the change does occur, the new host is ready to take over.