Essentially, to get smooth DNS propagation, what you do is have a functional site on both hosts, and then change your DNS settings (basically, change the A-Records) to address the new IP.
One hitch you're likely to run into in your current situation, though, is that the host with your shared hosting plan is probably also hosting your DNS, so you can't simply change their A records... You're going to have to move your Domain Name Server as well.
This will require changes to your base DNS server at your registrar, to specify a different DNS.
Depending on the registrar, I've found that this change tends to propagate fairly smoothly these days, but not as invisibly as just changing A-records. You may well have some down time.
I myself don't like to host my DNS with my web host. If the hosting company should have problems and you can't get through, you'll have problems setting up your site elsewhere.
Some registrars have very robust DNS setups with multiple servers, and in such cases I often use the registrar for DNS hosting.
Otherwise, I like to go to a DNS hosting company, sometimes setting up DNS failover as well, so if my main site at the web host goes down, the DNS company can switch my IP addresses to a backup site I've set up on another web host.