2
Flexibility, uptime, reliability and customer service are high on my list.
As far as features goes, I look for MySQL DB's. Not one, not 5 but 10 or more. (I currently have unlimited.) I also look for unlimited subdomains, unlimied pop3 accounts, lots of space and plenty of bandwidth for future growth.
Of course seeing my host stay up to date on the latest kernel, perl versions, php updates and sql versions are important to me as well.
Telnet would be nice to have on request if a provider/customer relationship trust can be established, but that belongs on my wishlist more then anything else.
A host that runs it's own Data Center is a BIG plus (mine does)
I shouldn't have to mention competitive rates.