1. Set up the new site at the new address on the new server.
2. make the DNS change of nameservers etc
3. Leave the old site up in place (or if you are changing domain name you need to put in place a 301 redirect match which send requests for a page on one site to the equivalent page on the new domain.).
4. Do NOT take down the site from the old hosting until the spiders have stopped visiting.
Spiders track IP locations not domain names, so until it fully propagates across all their datacentres they will go to the old location. if the site is not there it will be recorded as a 404 error, and Algorithms don't like 404's, it lessens the trust factor for the site. It is for this reason mainly that people say moving your site causes problems. it is not the moving of the site, it si HOW the move is handled
If you are switching domain names, then you can expect a time lag for the trust factor to come back and you get all your link benefit back. This can take anything from 2-12 months. My advice is, if you have a domain that is ranking well across the board, you need a VERY good reason to change it.