Do yourself a favor write a list of things the site will need access to.
SQL (MS SQL, MYSql, PostSQL)
Webserver (IIS, Apache)
Control Panel
Language (ASP, PHP, Cold Fusion, etc.)
Mail (Exchange or Sendmail; will it be hosted on the same server or a different server)
Bandwidth (What kind of site this is, est. traffic per month)
Co-Location or dedicated server
Operating System desired (Linux, Windows, Mac OS, etc.)
Speed required by company (They may want more than a dedicated T1)
Fault tolerance (Dual server configuration or RAID configuration)
Backup solution (Cron job ran every MWF, Incrimental TTH, etc.)
Level of support on hosting provider vs. paid technical support from company
Another important thing is budget, how much your willing to spend a month.
Really, the list goes on. Start with that, and if you can post the results