Ryan posts all the good points. Remember, uptime is king! No point having amazing support if you can't keep the servers up. So 99.8% uptime should be a minimum requirement. Ask for uptime stats for the last 3 months so you can see how the servers are really doing. A host's forum is a good place to hang, gauge opinion and you could also join up and ask a few questions. Lastly, there's no point in having excellent uptime if the servers are oversold beyond belief and crawl along like an alcoholic snail. Server speed, server uptime and support are the only things you need to worry about. If a company is doing those 3 things very well, it doesn't matter how established it is as it will succeed.
██ Laurence Flynn @ atOmicVPS LTD ██ Linux & Windows Cloud Hosting Solutions Powered by OnApp
██ Fully Managed [Shared] ► [Reseller] ► [Cloud VPS] ► [Dedicated]
██ Featuring the atOmicSTACK™ ● Speed ● Performance ● Reliability
fast and friendly support, at least 99.8% uptime etc
Dixiy.com - Professional Web Hosting Provider since 2002 AutoCreation.net - Automation Solution for cPanel Hosting! + Illegal File Scanner WHDir.net - Your complete Web Hosting Directory with Hosting/Server Tutorials
Laurence (aka NexDog) is right. One more thing I have to add. If the servers are up and running smoothly, the support will have much less tickets to answer to; it won't be swamped in "the xyz server is down!" kind of things.