I recommend http://www.slicehost.com/ I was blown away by the simplicity and power of their service. All the benefits of your own box with far less hassle and only $20pm starting fee. Loads of really good documentation on getting a production RoR environment up and running too. They're probably the best bet for bootstrapers and students.
Re: What webhost do you use for your startup?
#21madmotive, could you drop me an email? I've got a question for you about this. My email address is on my user page. Thanks.