I'm a big fan of Quantact for shared Virtual Private Servers, I have two servers with them right now, they're so afforable, and really good customer service. I'm using their cheapest option, the 96MB server, which is amazing at only $15 bucks a month.

But, with Ruby on Rails, I'm finding that the 96MB just isn't cutting it, so I'm thinking of upgrading to a dedicated server for my production sites. Still debating it, but Meganetserve looks pretty good, and some good reviews for them.