Amazon (and others) will sell you time on a massive grid. Amazon's is called Elastic Compute Cloud (EC2), and it seems like it might be a good alternative to a VPS -- the elasticity of each instance would be a boon to a quickly growing web service.
I am currently developing my startup's software on a dedicated server running FreeBSD, and I am paying some attention to making it so it will scale (probably in a load balanced cluster).
To this end, I have set up FreeBSD jails (low overhead chrooted full installs) so that I can test splitting up the application in various ways.
I would imagine that a transparent grid system would reduce the need to worry about scalability issues for many uses.
http://slicehost.com
I stumbled upon them last week after looking for an inexpensive dedicated server or VPS with root access. They offer slices of 4-processor RAID-1 Linux boxes (with your choice of distribution) for reasonable rates. You can add slices as you grow, up to the point of requiring a dedicated box. This is not a managed service--you have full control over your set up.
They are developer centric, appear to have a great community going and have received entirely favorable reviews online (at least as far as I could find). They are very Rails friendly (their interface is developed in Rails), but also support Python, Java, PHP, LISP, etc. With root access, you can install whatever development/server environment you desire.
I'm just getting set up, but so far, I have been very happy with their service.