Level 3 VPS at Hostgator is great for a startup and only around $40/month.

I've been using Hostgator for ~2 years and I can only imagine leaving if I plan to run my own servers.