Moving your site should be a snap if you have everything put together properly. Here's a good checklist that I like to use when transferring my clients data. Of course there might be a few hitches or glitches here and there with a new provider but if everything is in order it will make it much smoother.

With The Current Host:
Create a folder on your desktop.
Access your account via FTP
Need a great FREE FTP client go to SmartFTP.com
Dowload of your site's existing content to the folder on your desktop.
Backup any databases you may need into another folder on your desktop.
Finished

At The New Host:
Signup and get your control panel access. (As a security precaution use a new username and password with the new host!)
Log into the control panel and re-create your email accounts.
If you need Frontpage or extensions make sure they have been enabled in your control panel or ask the host to do it for you.
Look through the control panel to get familiar with it's functionality and features. Enable anything you think might be critical to your site's functionality. If you don't what those are you're in trouble to start with!
Then after that is complete upload your site via FTP from the folder on your desktop.

Important: If you are using cgi, php, asp, or other scripts or software you will need to reinstall and configure them. This is the reason you backed up your databases. Use the DB backups on your desktop to do this. If you don't know how to reinstall them ask your host to do it. They might charge you extra but it's worth it to make sure it gets done properly.

You should have a "temporary URL" to work with your site and get all this done BEFORE you change nameservers from your current host to your new one. If you don't get that ability get a new host! Once everything is up and running right on the new server you can change nameservers.

This is the "no downtime" method employed by my company and many others. I may have missed a few things in posting but I am sure some other hosts might chime in with their comments too.

And no you will never need a dedicated IP for the search engines (it's one of the oldest SEO myth's) but using this method will ensure that your site stays online through the nameserver changes.

By the way Verisign has stated that after September 8th those changes should take less than 5 to 10 minutes.

Good luck!

Joe