Well I used moniker for my domain name, but I'm not using a paid hosting site (yet). I'm sort of trying out 110mb.com since they are free and don't place ads on your site, and the reviews for them haven't been too bad. Unfortunatly I've not had the time to really devote to working on this much so I haven't had a chance to really try it out to see how good/bad it is.
The one piece of advice I recieved when researching hosting sites and registering domains, is to go through two seperate companies for each. This way if you have a problem with one, you still have the other one, and don't loose it all in one go. A number of comments I've read is that your better off not getting hosting from a company that primarily does domain name registrations; usually the hosting service turns out to not be that great - again from comments on a number of forums and sites I've visited. Hence I went ahead and went with two seperate services.
Also google any company you are thinking about going with and see what kind of comments there are. GoDaddy for instance was mentioned above, and I've seen both good and bad comments about them. So you really have to read what you can find and take it with a grain of salt, then decide what will work best for you.