I look for their customer service (24/7). Their average up time (99.9%). I also want a host that provides a ftp client, so I do not have to call them to make changes to my clients' websites.
I like GoDaddy. I use them for all of my clients and they are very good, reliable, and relatively inexpensive, but do not pay full price because they always have discounts. If you build websites with Joomla they are the best because you can download Joomla in about five minutes as an application.
If you are looking to partner with a host make sure they are reliable because this will reflect on you if a client's website goes down.