[rms]

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.

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.

Is there anyone using enough bandwidth on Google App Engine to hit the bandwidth cap and start paying?

[dangoldin]

But with Microsoft you'd be stuck using Windows Server, ew.