Same thing that makes any good company rearlly.
Reliability your never going to get 100% uptime but something above 98% is a bonus.
Customer Focused ( Works well when things are going right and wrong )
Cost - you know how much you are willing to pay if the price is right then do it.
Bandwidth - The more the better the bigger your website gets the more your going to need but start off small most hosts will allow you to increase it as your website grows.
Space - Small websites need small space large websites need lots of space

if your planning on loading it with images then the space will soon fill up. Hosts offer between 30-50meg this is ok for a small website but it never helps to have lots of spair room. If you develop your website offline you should know roughtly what your website is using.
Features - Make sure the core features you want are there for me this is PHP and MySql but theres nothing wrong with having a feature packed server sure you may never use them but if its not driving the ocst up then so what?
Before deciding have a look round and see what sort of name they have, rwead their forums to see how releiable they are then make a choice.
Also remeber your not making a life decision here if your only paying £20 a year and find out the host is pants then theres nothing to stop you moving it doesent take long to switch hosts.