Actually a VPS is good advice if you get one that fits the budget. You have to shop around because prices vary widely.
They give you just about all the advantages of a dedicated server for a fraction of the price. Being able to do what you want ,anytime you want eliminates many issues. You can also run as many domains as you want so the price can be less than some shared hosting.
This article has some tips for shopping for a host:
E-commerce - Getting Started Guide