They also give you a free SSL cert with your domain, and their UX for things beyond purchasing the domain doesn't suck.

+1 to gandi. They also have a nice DNS versioning system so you can track all your changes.