If you're looking to scale (as in, you need at least one dedicated machine and will likely be adding more), I highly recommend Softlayer. Their pricing is reasonable and support is pretty good, but more importantly (for my startup) their setup time is incredible. Adding a low-end machine usually takes about 2 hours and higher-end machines take 4-6 hours. That kind of agility has really been invaluable.
If you're just starting up, Slicehost is generally considered the best of the VPS providers, though Linode is also well regarded and is cheaper than Slicehost.<p>If you want to scale bandwidth eventually, Amazon is the only game in town unless you want to beta test Google. Maybe Microsoft would also let you beta test if you asked nicely.<p>Is there anyone using enough bandwidth on Google App Engine to hit the bandwidth cap and start paying?
I use and would recommend ThePlanet.com and Slicehost.<p>I use and would not recommend Mosso or MediaTemple.<p>I use and would conditionally recommend PHPWebhosting.com, Google App Engine, and RackSpace.<p>I use and do not have enough data to comment on AWS.