I think you need to be a bit more specific about what you will want your host to do. For example, do you just want to host a very simple website with relatively few visitors, or are you going going to have high bandwidth and resell websites that you design with a database and CMS and all kinds of stuff?

Currently I'm using www.1and1.co.uk (BTW if you decide to go with them let me send you a referall link) and they have been reliable though I don't think they are the cheapest. Prior to that I was with WebFusion, who were reliable but expensive for the package I had, but look cheap for simple packages.

Along the way between WebFusion and 1and1.co.uk I tried a very small provider who despite what the advertising said was a complete disaster.

Good luck.

Paul