I've had the opportunity to use a lot of different web hosting packages over the years. This is partially due to the clients sites I get to work on and partially due to the number of web hosts I've personally used. With many of them I run into problems that suggest the hosting company just doesn't get what we want to do with the web or that they need to work on the fundamentals. Here's my short list of things to look out for when choosing a host.
SSH Root Access
There are a couple hosts I'm aware of that allow root ssh access to their servers. I don't mean just master access to the account but, actual root access to the server. What happens when you mix this with weak passwords? Scary things, like servers being hacked.
I consider this the lest scary thing on the list. If you have root access you can turn off root ssh access fairly easily.
No Actual Backups
From time to time bad things happen to the hardware hosting our sites. Hardware fails and sometimes you get hit by it. That's what backups and redundancy are for. But, what if your site crashes and burns and when you go to get your backups you find out the advertised backups aren't really there! I've seen this and seen people loose years worth of content.
There are two things you can do about this. First, search Google for any horror stories about the host your considering or using. Some of the people this happens to are vocal. Second, do your own backups. They aren't that hard and when something goes wrong they are entirely worth it.
Failed Security Practices
In one year I learned of about 10 different sites being hacked on the same host. If it were just a few sites it would be easy to blame brute force attacks and simple passwords. But, that wasn't the case with these sites.
This was a matter of failed security practices and updates. A host had been lazy with those and it cost those sites some embarrassment, pain, and money.
Many of the sites I work on have image manipulation of some kind built in. This could be as simple as resizing or cropping an image. In PHP this is fairly simple with the GD library built in. That is, unless you are on a host that has removed it or is using the systems GD rather than the one built into PHP (this cripples some features).
Utility program screw ups like this tell me a host doesn't get what I'm trying to do or simply doesn't care. If that's the case there is a better host out there providing the features I need.
Google Is Your Friend
The best trick in my arsenal for choosing a host is to take a few minutes and Google a host searching for their dirty laundry. These are just a few of the things to look for.