I just started using http://prgmr.com/xen/ -- a (much) lower cost alternative to slice/linode... works great. It's a small company, but I couldn't be happier... the guy who runs it is active here.
This is wonderful. It looks out of my league though. I'm looking to learn by doing here, but that approach might be a bit much. (I have a soft spot for small businesses.)
linode is also a good option
Thanks guys. I'm sorry I didn't define cheap. I didn't realize how relative 'cheap' is. I think ~$10/mo is cheap, this site won't directly make any money. Slicehost and Linode look great, though I don't know my stuff.