Google App Engine. Until you've proven your business concept and scaled up, this will abstract the server away so you don't need to worry about it.

I've looked at that and probably will do that for dev/testing. Is it worth it to stay there and start paying after you've proven yourself or is that the mark to move on?

Good question. GAE isn't without problems of its own, but at first glance looks good enough to scale to millions of users. I've never had a project that has done that, but it seems the time to move on is when you run into issues with it that you cannot overcome.

Webfaction - highly regarded, good support, lot of convenient features

I have over two dozen clients running on WebFaction right now with excellent results. Django and Plone mostly.

When I need more control over the environment, like caching or long-running background processes, I go right to SliceHost or Linode (sometimes EC2).