Id say you should answer the following:
What is it for? home/development-testing/business/personal
content? is it legal? images / video / streaming? / blog / forums?
Your budget? Will it require a database? is it going to be dynamic?
what database will you require? MSSQL / MySQL /Access / Oracle
what language needs to be supported? ASP.NET / ASP.Net 2 /ASP / CGI / PHP / FrontPage Extensions /
How much traffic will it have? how many people will visit a day / month / year
what kind of domain name do you need to register? .co.uk / .com / .jp ???
There are many more questions you should consider, I would at least answer my list above.
Two decent hosts:
http://www.easycgi.com/ 350 GB disk space
3,500 GB Transfer
PHP, ASP, .NET 2.0
$7 a month
http://www.fasthosts.co.uk/ Web space 1.5 gig
Website traffic Unlimited
ASP / PHP ASP.NET 2 Databases
Email accounts 200+
Load balancing optional optional Included
Monthly fee £3.99