I recommend that you not host DNS with your registrar. And if possible, that you not host DNS with your hosting provider (although, that can be more difficult).

If you have a high value domain, you might want to look for a corporate registrar, like MarkMonitor or CSC, or anyone else who can do Registry locks (which are very different than registrar locks and are rather inconvenient, but potentially very useful); but know it's going to be expensive. I also had a good corporate experience with register.eu, they've got a lot of ability to satisfy foreign presence needs for restricted TLDs, if that's something you need/want. If it's a low value domain (like my personal domains), I don't have strong feelings, except for the love of whatever you hold dear, don't use Network Solutions; they were a fine choice when they were the only choice, but ever since we had options, they should have been used. A lot of registrars are really pushy with upsells and what not, so I've tried to go with no fuss registrars over the years.

In terms of DNS services, I don't have any particular recommendations; I personally run my primary DNS on my hosted machine and secondary with Hurricane Electric, which is free for my usage. There are (or were) several free secondary DNS services out there, but the one I used to use stopped maintaining their website (TLS 1.0 only, certificate issued 2014, expired 2015) and I already had an account with HE's tunnel broker, so it seemed like a reasonable choice. I still have a domain I host for a friend that uses that old service, because I can't get my friend to update the glue records at her registrar; the service still works enough, I guess.