I think Canuhead has the best suggestion so far, to see Nfld in a separate trip from NS, PEI and NB. Combining NB, NS and PEI makes good sense from a travel standpoint - you can drive into NB and drive the fixed link onto PEI, then take the ferry to NS.

Since I live in the Maritimes, feel free to ask away if you have questions about the area and I'll do my best to answer them.