I'm started renting a dandy server in America for $13 a month. It's pretty sweet. Full root access. 128MB ram. 5GB hard disk space. More bandwidth than you can poke a stick at. I moved this blog there yesterday, and it took all of about 10 minutes. I might move more important things there if all goes well.
One of the fun things is that you can install any of about 15 different Linux servers onto it with a little click. I've already been through two versions of Ubuntu and a version of Debian vanilla. I'm thinking I'll stick with Ubuntu Dapper now though. Seems pretty sweet. Lighttpd is finally in the repositories.