Rails hosting (Virtual Server)

I've actually been using http://www.stevensonsoftware.com for VPS hosting. Its very affordable and the support has been great. I got up and running in minutes. I pay $40 / month for the "Large" plan (512mb RAM, 20gb storage, 80gb bandwidth). That costs less than the other services you were asking about.

Hope this helps. -Scott