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 agree, my friends actually just switched off MT because of their difficulty hosting RoR apps.
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.