[detourdog]

I have been with network solutions for registration from the beginning and panix.com cheap-web for primary dns.

http://www.panix.com/web/

They are actual unix sysadmins and very easy to deal with.