I highly recommend Slicehost. I've been amazed with their responsiveness, availability and competence.
I'd sign up right away, but we are using facebook for our social aspects, so we probably qualify for Joyent's free accelerator (for a year). That's a pretty tempting offer, even if I have to learn Solaris.