Heroku is simple and great for playing around with apps in production mode but rapidly becomes very expensive and as it's a PAAS you are limited as to what services are supported and indeed many services that you would normally just install for free on a VPS are charged for to some extent o Heroku..
There are loads of hosting option available to you, I recently moved from RailsPlayground VPS (Fantastic host that I would highly recommend with live 24/7 chat support as well as ticketed support) to Linode after playing around with Rackspace and I have been very impressed with Linode.
There is no support on Rackspace unless you want to pay, Linode has a superb community with irc and forum help freely available and Ryan Bates has a very recent Railscast (http://railscasts.com/episodes/335-deploying-to-a-vps) showing how to set up an Ubuntu production server on a Linode.
Hostgator also seems to be highly recommended quite a lot by rails developers on this forum. Steer well clear of the main stream non dedicated rails hosts as most don't have a clue how to serve a rails app properly.
What you want and what you need are too often not the same thing!
When your head is hurting from trying to solve a problem, stop standing on it. When you are the right way up you will see the problem differently and you just might find the solution.
(Quote by me 15th July 2009)