Does it have to be a specif ruby/rails-hoster like
http://www.engineyard.com/ (or highlevel l ike
http://www.heroku.com/) ?
I would just go with a small VPS from wherever and then beef it up or buy a dedicated server once you need the extra power. Installing ruby,rails,nginx with mod_rails isn't much work.