If you have server space already where you can do all your own stuff such as DNS, I suggest domaininvestigator.com. If you have no idea what I just said with regards to DNS, then godaddy.com is top notch.
Also, be careful searching for domains. There are some funky things going on out there right now with some of the registrars - if you search for a domain it will apper taken in about 24 hours. So, best to come up with some names and then when you are ready THEN search to see if they are taken and get them right then.
http://www.eweek.com/article2/0,1895,1991365,00.asp
Also, think about getting the .com, .net and .org domains all at once. It will be much cheaper if you use any of the cheap guys.