I like Slicehost. I have tried Joyent and it's good but you have to learn a bunch of Solaris skills and many gems don't work quite right on Solaris, and I've tried Engineyard but nobody will return my emails to set up an account.

Slicehost has never done anything but offer consistent, professional service. I could not recommend them more highly.