I'm checking out Heroku, which seems appropriate for my level. Gracias though.
It's basically a full Linux server, except it's really a virtual machine running on something else. That's just an implementation detail, though.
Anyway, I use Slicehost and the service is great. Very easy to manage via their web interface, and the price is not bad. $10/month for daily and weekly full backups is also a plus. If I fuck up the server miserably, I just press a few buttons and I am back to last night's unfucked version.
The only downside is that they only accept credit card payments, but considering what they are offering it's not that big of a deal.
Heck, this very page is #3 on Google for "linux slice" which shows how little the term is used ;-)