I am going with Media Temple (GS) I can't give you feedback about them yet, but they cost $20 a month and their grid server can grow with your needs...
I recommend doing a Technorati search on that. Lots of people have received less than reliable service on the Grid. They do great marketing, but their tech is overrated from I've been reading.
I've launched two Rails apps on MT(GS) and my experience has been very good. I believe they did have some issues initially, but I can say that I have not experienced any of the problems others have had.
