Depends on the type of hosting.

One fairly common issue is making sure the old and new servers have the same versions of software, or if software is to be upgraded too, making sure there are no compatibility problems with client websites, etc. Configs need to be transferred across too.

The new server should be able to take over the old IP address(es) when the move happens.

Downtime's an interesting one. One great thing about VPS is that with the right technology, and old and new servers running side by side, clients can be live migrated and no downtime is seen. Shared hosting can benefit from this too if running on a VPS. I guess it's hard to be so seamless with dedicated servers but it still shouldn't take several days.