It is hard to give you advice like this. What software do you plan to use for your webiste? Do you plan to use CMS? If yes, which one do you prefer? Which programming language do you need? What will be the site about? If it's video hosting site for example, then you must go for a company that offers lot of space and bandwidth plus streaming support. You see, it all depends, not every website is the same, so as the hosting providers. You can take a look at this poll:
Who's the best host, to check for most popular companies. But, remember there is no point in searching for the best web hosting company, instead search for the appropriate company for your website.