Choosing a host can be tricky. I suggest that you go with a low monthly amount, but make sure that you have a cgi-bin. A cgi-bin is important if you want to have interactive functions like a form people can fill out and send to you (formmail).
If you're going to be doing e-commerce, make sure you can upgrade (for zero or little $) to an account with a database (mysql).
Make sure you have access to your raw stats. With a good traffic analyzer (FastStats Mach 5, etc...) you can download your stats and run your own reports, as opposed to relying on a host's slow, clunky and limited web dashboard analyzer.
And don't be afraid to jump from one host to another. If you can find a host that charges you month to month, as opposed to year to year, this is best because they are more likely to be on their toes, as they know you can bolt at any time. Which leads to my next item:
Don't be afraid to bolt to another host. Some people will say that it endangers your rankings, but not in my experience.
Not sure if this is too important, but it's worth thinking about: Make sure your host servers are in the United States. IP addresses are assigned regionally, as I understand it. So, you have Euro ip addresses, North American, Asian, etc. But this statement is qualified.
Buy a computer magazine and see who's advertising their hosting in the back of magazine.
Don't believe everything you read in online hosting web sites, because some of them are nothing more than vehicles for ads, and their recommendations are paid for.
And if you are non-adult related, then make sure your host states in his/her terms of service (tos) that adult sites are not allowed. I wouldn't want to have my site share an ip with an adult web site, even though I know that search engines are able to resolve shared ip's. There can still be an ip ban out there, and you will be out of luck.
