The big thing for me is the uptime, and reliability, alongside good prices (in comparison with quality) and I also like to see some good support just for peace of mind.
I like Vpsblocks.com.au as my web host. They've handled every ticket quickly, and with the responses you'd want from the very start. Speed is good, and the price isn't bad at all.