You should not need to endure any downtime, even though DNS changes can take days to propagate. The trick is to get DNS working at your new host BEFORE you point your domains at the new host's servers. This way any given person will be hitting the new server or the old server, but it won't matter -- both should be serving the same information.

Other suggestions in this thread, such as reducing the TTL beforehand, will help drastically if any issues arise.