Depends on too many factors.
How big a site are you planning to build? How much are you prepared to spend? What level of support will you need? What features do you need? Will you be setting up other web sites, or just the one?
Also where are you based? Since I'm in the UK, I can only recommend companies I know, so I'll suggest companies like
Webfusion and
Skymarket might be good for setting up a large scale site. For a smaller site, you might want to find a reseller for one of those (ie someone who's bought a large chunk of webspace from one of them, and resells bits of it to smaller sites), as they'll be able to offer you a better deal with a smaller package.
If you're based somewhere else, a host more local to you would probably be better, of course. But at the end of the day, the questions I asked at the beginning will make a big difference to who you decide to go with: it's worth researching different companies to find out what they offer, and how they compare. What works for me may not work for you.