We live in Halifax but spend much of the summer in PEI
Here are some of my suggestions
In NS....consider Risser's Prov. park near Bridgewater. If you are lucky you may get one of the sites almost on the sand beach.
Kedji...a National park is great but can be a little buggy at times. Home to dwindling flying squirrels.
Graves Island Prov park is very near Chester (the Martha's Vinyard of Canada) and close to the ferry running to little and Big Tanacook Islands ( a ferry that serves a small population but is also a great day trip and begs for a picnic and or bikes to get around the islands)
Chester is about an hour outside of Halifax.
In PEI my fav camping is at the north west tip at the Jacques Cartier Prov park. Again, there are sites on the beach. One Ont couple that I met go there for 2 weks every fall
when there is virtually no one there. You can walk that beach maybe for 6 miles or more past the campground and not see a soul.
Cabot Prov park is very underused and the water is warm for swimming
I can hardly wait for summer!!!