For what it's worth, you can use Linode's rather awesome DNS hosting service if you want to. You'd still need a registrar, of course, but you'd delegate the domain to Linode's nameservers and manage DNS through Linode. Or don't use it; whatever. But if you do, it removes DNS hosting as a factor when considering registrars.
Linode doesn't have an officially-recommended registrar.
Go Daddy is the most popular -- and, of course, most-hated -- in the world. Aside from that, 'round here, I'd say people use
Namecheap,
Name.com and
NearlyFreeSpeech.net (which is really a web host).
Of course, what registrar is best also depends on what TLDs you're interested in.
There are also several other threads on this subject around here.