Bandwidth is hardly an issue. Most shared servers have a maximum connection allowance that is pretty easy to go over on. Of course they never tell you about that when they entice you with their unlimited* bandwidth.
Get a dedicated server and account for 24-48 hours of downtime as you get nameservers switched over. Research how to do a server switch beforehand so you don't encounter any more downtime than necessary.