I rarely see them mentioned but linode is probably the best deal I have seen. 19.95/month you get a VPS solution, full root access, 360mb ram, 200GB Transfer and they have awesome customer service. And no, I am not affiliated, its just nice to see a hosting company that serves its customers well @ Linode.com