I’ve started hosting all my personal sites at linode. I have root access to my own Virtual machine and I have installed Debian 5.0, lighttpd, mysql, and a bunch of Drupal and WordPress sites. I have found an incredible performance boost compared to shared hosting and it only costs slightly more. I’d highly recommend this for anyone with some knowledge of linux administration. The only downside is backups, but I solved that using backup-manager and creating an Amazon S3 account where the backups get stored (all very easy).
Check out the details at linode.com.
EDIT: Linode now has a backup solution that is simple and automatic – just what you want!