Definitely fly into Halifax, and plan to spend a few days there. It's a great city with lots to see and do. Rent a car for the duration of your stay in Atlantic Canada.
The Annapolis Valley in Nova Scotia will be beautiful at that time of year. I suggest spending a few days in Digby. From there, you can travel by car to Port-Royal, mentioned above by undercoverbrother, and other nearby areas of interest.
After that, drive north to Cape Breton for a few days, and then take the ferry to Newfoundland. Of particular importance: do not call anyone in Newfoundland a Maritimer. The locals are very particular about this point. The Maritimes consist only of New Brunswick, Nova Scotia, and PEI. When you also include Newfoundland, the correct term is "Atlantic Canada" or "the Atlantic provinces".
At some point, make sure you have a traditional Maritime lobster dinner. Pretty much every tourist town in the region will offer this amenity.
I'd skip New Brunswick completely, but I'm probably biased because I grew up there and take it for granted. It's definitely less interesting than NS and PEI, though.
|