I’d recommend looking for a host that knows its way around Ruby and Rails. A lot of hosts nowadays “support” Rails apps, but won’t be able to help you. A good source for reviews is http://www.railshostinginfo.com/
My personal experience has pushed me away from shared hosting, but I know some people on this list know shared hosts that do have Rails knowledge or even focus on Rails deployment. I’m sure they’ll chime in.
If you can afford it and know your way around Linux a bit, I’d recommend getting a VPS instead, this way, you’ll have root access and will be able to do as you please (including securing your linux VPS, so make sure you know your way around linux). I’m extremely happy with Rimuhosting, support has been so helpful I can’t express my gratitude with words. They go far beyond what you would normally expect from hosting support. Whenever I ask some advise, they have provided me with splendid information, as well as doing all the work for me in most cases. They also have a Rails stack ready if you mention it in your order (i.e. your VPS/server is already setup with everything you need to run Rails).
Slicehost has also been recommended by a lot of people on this list.
Search the archives, this subject has come up dozens of times already.
Peter De Berdt