Depends on how much time you have. In Nova Scotia the popular road to ride is the Cabot Trail (Cape Breton Highlands). It's spectacular. Do it counter-clockwise. Expect RV's and campers on this road up until September. We were there last May - before tourist season and it was empty. There are many great places in NS also. If you like history, consider Lunenburg.
Labrador is gorgeous, but best seen on a dual sport. But HWY 510 is very scenic, and paved, from Blanc Sablon (actually in Quebec, but the ferry dock to Lab) to Red Bay. After that, it's approx 500 km of gravel to Lab City.
I'd spend more time in NFLD. Nearly every road/Hwy stemming from the Trans-Can is amazing. Twillingate is a must as is Crow's Head and Gros Morne National Park! Try to get to St. John, and take the southern loop on Hwys 10 and 90. Watch for animals (moose), as this area tends to be foggy most of the summer.
PEI is scenic and you can probably cover most of it in 2-3 days. Cavendish beach is a worthwhile trip.