Others have suggested NearlyFreeSpeech.net here and so I signed up with them a while ago (switched from GoDaddy). I've been using it for domain registration, DNS, and web hosting. Since I have ~0 traffic, it's dirt cheap.
It's ideologically the polar opposite of GoDaddy. And the web interface is so much easier to use.
namecheap is highly regarded, and I've had good experiences with them myself. (In the interest of full disclosure: I'm not associated with namecheap or any other registrar.).
If you're interested in using Google Apps, you can register a domain name through Google and they will automatically configure Google Apps for your domain upon setup. http://www.google.com/a/cpanel/domain/new