I'd recommend namecheap or godaddy (or another registrar if you can find a cheaper price in your TLD space for new registrations). NC and GD are both cheap, and you can always transfer the name later (often getting a cheap renewal and free whois privacy).
As far as hosting, yes, agreed host somewhere other than your registrar is a good rule of thumb. In general. Depends a lot on what you're doing - hostgator or bluehost are pretty good for basic needs, some times hosting with your registrar can work out okay, but it's putting all your eggs in one basket. Something like hostwinds or servint if you're looking for something a bit better. Read around a bit on the web hosting forums (but obviously not the sites that are "review" sites that are just a bunch of affiliate links with BS reviews) and you can probably find coupons for them.
good luck - gregs.