I think support is probably support is near the top (if not top) of my list. It's no good having a great package if you can't get help when you need it. Support need to be relatively quick and helpful in attempting to resolve the problem. Probably the only way to find out how good support is is to ask existing customers, probably best on an independant
website hosting, as some webhosts (not here I hasten to add) censor posts.
Uptime of the server and it's various resources is also important. It's no good having the server go down regularly or be down for many days. Similarly email or databases going down is just as inconveniant.
A reasonable hosting package perhaps with varying price packages to meet your needs is handy. A 'one size fits all' package can mean you're paying for much more than you're going to actually need (or want). I would say 'value of money' package however in some cases you get what you pay for, in that whilst the package might be cheap you get poor support as a result.