I would get a Xen VPS since you get a guaranteed amount of CPU, RAM, disk, and bandwidth as well as full control of the kernel, firewall, software, etc. I've been very happy with http://serveraxis.com as well as http://unixshell.com but definitely do a bit of research first, http://www.webhostingtalk.com/ is a great resource for that.