Careful with the colo options. I've recently been comparing "colo" (you supply the hardware) vs. "unmanaged" (they supply the hardware). By the time you add up the cost for a decent 1U (or 2U) rack mount enclosure and internals, plus shipping it to the colo facility, etc it can be the same as a year of monthly fees for unmanaged. Plus, if the hardware fails it's harder for you to deal with it remotely. Most unmanaged services replace bad hardware within 24 hours.

If you want to try the virtual option (User Mode Linux in this case, there are other virtual options), this happy customer highly recommends Linode (www.linode.com). You have full root access to your virtual host, and can compile whatever you want. I use this as a backup server for several small services I manage. (DNS, email backup MX, etc)