If you have the budget, choose Amazon EC2. And until Amazon EC2 provides a good web interface to manage the server instances (I heard they have a web interface now, but not sure if it’s good), Rightscale might be a good choice. Rightscale has lots of documentation on setting up server instances for RoR, but I am quite sure this post will still help cut the time needed to finally launch your Rails app on Amazon EC2!
First of all, follow the Rightscale instructions here for preliminary set up.