Joyent Accelerators ( http://www.joyent.com ) are flexible, and they're the "official" Ruby on Rails host. They also happen to offer the best control panel (Virtualmin, of course). The only negative might be that Accelerators are Solaris systems--I don't have any complaints about that, but if you're accustomed to Linux, it might be a bit of a learning curve.

Slicehost ( http://www.slicehost.com ) has a good reputation. Their Xen systems are not over-subscribed and they know their business.

Media Temple (http://www.mediatemple.com ) had a good reputation until recently...but I'm sure it was a temporary setback. They're technically savvy. They're using a kind of quirky virtualization layer (Virtuozzo) which, when over-subscribed even a little bit (and sometimes even when not), exhibits serious memory issues.

Gridzones ( http://www.gridzones.com ) is another Solaris zones based host, and they have some reasonable plans. It's a smaller shop, so probably gives more personal service. Tell Phil that Joe from Virtualmin sent you (I dunno if it'll get you a discount, but he'll be happy to hear from you). They start at $15, which is hard to beat (you probably want more space than that, though...). They're also Virtualmin friendly, when appropriate (i.e. when you have enough space/memory for full service hosting).

If you're wanting to spend a little more, The Planet and Server Beach both offer dedicated boxes starting at around $69, I think. I've used both for years with very few complaints.