id go for one of the bigger boys my self - 123-reg do a good service - also they let u edit all your dns records online.
depends what sort of hosting u need windows? asp? blah blah blah
a load of stuff to consider..
interland are very good btw, used to use them for a big project for a few years.