Troy is on the ball again, youll need to list all the features you NEED, all the features you WANT, all the features you can live without. Think about how much you want to spend, also how many websites/domains you would like to host.
This site and a few others are running on a VPS (Virtual Private Server) from LiquidWeb at US$50 a month. They have been pretty good, and have all the features i need, php, mysql, cpanel, fantastico, and a few others. Sometimes the speeds are a little slow, but other than that, pretty good value for money.
If you have a bit of money to throw around, then id definitely suggest Steadfast Networks, they have been serving my brothers company well, with about 10+ servers, any problems are dealt with fast and efficiently, and any upgrades are done in a timely manner.
There are so many web hosting companies to choose from and a lot of people have had varying experiences with them, check out the great forum over at webhostingtalk.com