Stability, speed, a unix flavor. I don't really use support that much.
A "something's broken, come and fix it"-button is all I actually need from support.
A basic package consisting of some webspace (not a gazillion megabytes, just 50 or so would do at first) which can be upgraded at an acceptable rate. PHP support and mySQL is a must, perl, some pops, mailing list.
Bandwidth should be affordable, like 4-5$/gig max.
That's about what I look for in a host. I don't need all the bells and whistles since I don't use half of it.
A control panel is a plus.