The best domain registrar of which I'm aware -- everyone I know who's used it has been happy with it -- is http://nearlyfreespeech.net/. I've also used DynDNS and been very happy with them; someone else mentioned them as well.
NFS doesn't make it obvious that they do domain registration -- you have to click through to "services" to see it.