If you've got some experience in server administration, slicehost.com is the way to go. They give you root on a custom Xen virtualization slice that you can rebuild to whatever OS you want that they provide - Arch Linux, Ubuntu, Debian, CentOS, Gentoo, etc - and you can set it up however you want. I've got one that's 20 bucks a month. It's great if you don't need a bloated control panel and lots of pre-installed, out-of-date applications.
Also good because you can install whatever you want - PHP5, MySQL5, Apache2, Lighttpd, everything. 🙂