Yarmouth has a bunch around town that are easy to do a walking tour. There is a nice series “Cape Forchu Series]” southwest of Yamouth. Very nice scenery. From Yarmouth to Shelburne there is a “power trail” called welcome to the Boonies (search for “WTTB”. It is about 200 caches that range from PnG to hikes to puzzles to multis.
Going up the coast from Shelburne to Halifax there are numerous beaches. One of my favourites is Carters Beach. Look for GCKWFK.
Along Highway 103 there are many caches that are PnG at almost every exit
At East River,exit 7 on highway 103, is the oldest cache in Canada placed June 28, 2000. GCBBA.
In Halifax the are lots of caches, typical urban stuff as well as parks and trails. Point Pleasant Park in Halifax is a nice walk and has a few caches to find. The boardwalk on the Halifax Waterfront is enjoyable and there is fun multi that is disabled right now GCKC9G. There is a lovely Rails-to-trail in Dartmouth called Cole Harbour Heritage trail that has awesome views and plenty of caches here is a map http://www.trails.gov.ns.ca/SharedUse/hx124.html . As mentioned already there is Peggys Cove which has some wonderful scenery.
To observe the Fundy tide I have an earthcache to watch the tidal bore GC11FBK.
Again there are lots of caches to do on the way to Cape Breton. Take time to do the Cabot Trail, not many caches but breathtaking area Nice little side trip is to Uisge Ban Falls GC1FZ0P. Awesome cachers up there.
In PEI I haven’t done a lot of caching but every one I did do over there was great.
In NB I recommend some time in Moncton, the home of the Uber Cachers. You literally can’t swing a dead cat without hitting cache.
Hope this helps, I am sure I am missing stuff and this is a very quick overview. Let me know if you need anything at all