J.D.,
You might check us out at http://railsboxcar.com/.
One of our guys just did a short screencast showing off our deployment process.
* http://screencast.com/t/9UoB8oYy
Cheers, Robby
I have a virtual server with slicehost. They are quite good so far for what I need and keeps the cost low. I would also look at mosso, who own slicehost and offers a pay as you go version which works out cheaper.
Nayeem