Overselling - most hosting companies oversell. This can mean that you get several years of good value, but that may erode as they begin to take on more customers than they really can handle. Some sites guarantee they don't oversell. Look for these if you want a long-term solution.
Reliability - obviously you need a site that is up most of the time (sites require occasional maintence or upgrade time during a given year). This can be determined by reviews of hosting sites on the web (see below under Reviews for some popular review sites).
Service - this is a little more difficult to determine before you sign up, but you probably want a site that is supported by English speakers that you can understand. Technical problems are difficult enough without language barriers. More importantly you want a site that has decent documentation and that answers your emails or calls promptly.
Tools - A site should provide good tools for you to maintain your email addresses, files, and databases associated with your site. Site statistics tools and functional add-ons are also valuable. CPanel is provided by many of the more capable hosting companies. Fantastico or Simple Scripts is usually available as part of CPanel and either one provides automated installing of many popular tools. This can be a real time-saver. Fantastico and Simple Scripts differ slightly from provider to provider in terms of what products it supports and the revision levels of those products.
Price - this is the least important of these parameters at the level of the individual web developer. Even the most professional hosting companies provide hosting plans starting at around $100 per year including the domain registration. Usually you can run several (or even unlimited) domains from a single account - so buddy up with a friend/group you trust if you need to save money.
Note that we are not personllay recommending these as we have not used most of these. However these are choices that appear highly rated.
Remember to check the dates on all reviews - a site might have been great three years ago but has lost its edge.