I can't recommend Slicehost enough. They're not cheap, but my sleep is expensive, and I can't remember the last time I lost any as a result of hosting with them.
Slicehost is good, but if you don't have any investment with them yet, Linode is good too, and significantly cheaper, without, as far as I can tell after a number of months with them, being any worse in any way. This is mainly due to the fact that Slicehost forces you to use 64 bit, whereas Linode lets you use 32 bit. If you took away that difference, they would mostly be equivalent.
I have a slice and also a linode instance and they are both good services. Slicehost is easier to make instances but linode offers you more configuration options. Both are great services though.