How we got hosted, the Rails way
blog.wakoopa.com
blog.wakoopa.com
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.
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.
I've been very happy with Future Hosting at http://www.futurehosting.biz/. I've got a VPS with Ubuntu on it and we completely control the box. We're paying $25/month for that server.
What you trade off in control you make up for in free time. Granted, as you get larger and develop traffic, the trade off will need to be re-evaluated, but I don't see any major benefits at the beginning.
So my advice to anyone hosting a Rails app or any other web app would be to go with a dedicated host (where you at least have a virtual server or something)