Slicehost
Two words: fucking awesome.
I would leave the post at that - but alone those words don't carry much weight around here. Why is it awesome? Well, for $20 a month you get a complete VPS with 256mb of RAM. It doesn't seem like much, but coupled with the Slicehost manager and the fact that your slice is completely isolated on the host server from other slices (the other slices can't grab up memory or CPU cycles from the host server) makes Slicehost totally awesome. The main site lists all of the features exhaustively, so I don't really need to go into that.
I only was vaguely familiar with the Linux console when I started, as the only experience I've had with it was with a Freecom NAS over SSH and a Pentium 2 (which could be considered a plug-in calculator).
Slicehost has you covered though, from PHP/Apache2/MySQL installations to nginx and lighttpd and FastCGI available over at the Slicehost Articles site.
I personally went for Ubuntu 8.10, which is dead easy to work with by way of aptitude. I did try playing with nginx and lighttpd - but I couldn't get nginx working with PHP, and lighttpd was significantly slower with PHP than Apache 2. In the end, I decided that I would use Apache 2, even though it is a memory hog at best.
SimpleStats.net was completely switched over to my slice a couple of days ago - and it has been chugging along nicely since. I owe all of the speed improvements on the site to Slicehost, as even from here in the UK loads the homepage in ~160ms, and at present I've not employed any caching on it.
To save the server starting extra Apache processes when requesting pages I've moved every single external resource over to my Amazon S3 (mirrored by CloudFront) bucket, which I think is pretty useful in terms of memory management.
I've also moved all of my current domains over to Slicehost's DNS servers, mainly because of the extra control I get over every single record that I don't get with my shared hosting but also because I think in the long term they are going to be more reliable than the nameservers at A Small Orange. Of course the *small* incident that occurred the other day may have slightly influenced this decision. That, and the apparent constant crashing of Apache on this server that has been frequently occurring over the past few days.
Backups: The backup service costs $5 a month, and gives you the option to save a complete image of your server manually, or schedule a daily and weekly backup. I took one just after I configured iptables and created a user account, and I'm also taking daily and weekly snapshots of the server should I fuck it up big time. Which is probably going to happen.
One little problem with the backup manager is that the backups are stored at Slicehost, and you can only have a maximum of 3. I do understand the amount of bandwidth they'd need to allow customers to upload/download complete slice backups, but I think it should definitely be a direction that they consider. For now though, the slice backup system is completely adequate for my needs.