As a host myself of some 8 years standing, and a Unix admin of nearly 30 years standing, here are some differentiators that I’ve come up with over the years:
Make sure the host is running something that logically separates accounts, so they can’t access each other’s files and databases. This is called phpsuexec in simplest form. If your PHP runs as DSO under a user like “nobody” then you can access all the other PHP files on the server - not secure, and really open to abuse and data theft; have seen it happen with some of our clients.
Make sure the host does backups (yes really!!), that they are automatic, regular, and are rotated. One daily and one weekly isn’t enough - what if you get hacked? How long does it take them to restore?
Make sure the host runs a firewall of some sort, preferably an active firewall like CSF, that will block hackers. This limits your site’s exposure to hackers, who work systematically through their exploit libraries until they compromise your site.
Make sure your host runs something like mod_security with at least a rudimentary set of rules. This blocks many standard attacks (eg SQL injection).
Check that the host has some sort of data redundancy - do they run mirrored disks, etc. Do they have some sort of fast emergency restore strategy, on slow or large servers a restore of cpanel tarball backups (for example) can literally take days.
Don’t get too excited about large disk and bandwidth allocations - at the end of the day many of these hosts will kick you off for TOC violations if you host anything other than small web files, eg ISOs, large zip files, movies etc, all of which can sometimes be parts of sites.
Don’t expect to pay bottom dollar and get away with it forever - at the end of the day, one always gets what one pays for in one way or another! 
Be careful about going with a one-man (or woman) band. It’s harder for them to make it work long term, unless they’re really technical. “Harder” does not mean impossible, I know there are some great one person hosts out there who have clever contingency plans in place and provide great service.
If they fail financially, what will their strategy be - will they close shop and run, or will they sell to someone reputable who will look after their clients? This can bite very hard, and many of our clients had former hosts who disappeared overnight, taking their websites, with no chance of file recovery.
Oh - an important one - are they a reseller or do they have their “own” dedicated servers? Reselling is OK, but the parent company’s backup is always important.
One that is usually OK is - do they have server alerts if their servers go down overnight? or do they wait to get told?
I’m not a big one for 24/7 support, as many times companies claim to have it but all they have is an after hours Indian answering service, which can’t actually resolve real problems. I don’t claim that for our company as I have an ethical problem with saying we deliver something we don’t, even if it would bring in more business.
Don’t get caught up with the “overselling” thing. Everyone “oversells”, it’s more about whether hosts do so excessively, thus making the servers vulnerable to overloading problems. If a server has more than a thousand accounts, it’s just asking for trouble, although I tend to prefer to be much more conservative - having a few more servers is less expensive than having to run around dealing with performance problems all the time in my mind.
I realize this is getting pretty detailed - and that you may not actually be able to ask these questions in real life - but I hope it helps!
Here are some of my thoughts in one of our blog entries on this same topic - hope it helps: What’s special about our hosting?
Oh - one final idea: sometimes partnership with a smaller company gets you better service. Just look for the indicators of stability as well.
