I would normally look for in below order:
Support (Technical support is very important), Value for Price (you will get what you pay for), Uptime, Reliability
I've been with kvchosting.net for just under a year...their support is good, they always respond within a few hours, and often within a few minutes. Their servers are pretty good!