Hi,

I live in Moncton New Brunswick and have traveled 2 times across Canada from Newfoundland to Dawson City Yukon. I can help you navigate through Canada with ease.

Here are some things to consider:
1. Arrival...you say May and in Halifax...exactly when could be helpful in helping you understand the climate and what to expect.
2. Upon arrival where do you want to go first? Newfoundland the furthers most province in Canada could be a nice starting point however that time of year it could be very cold, but I would recommend doing the Cabot Trail...most would suggest doing it counter clockwise as you get better views. Both of these places should be considered depending on your arrival time. The latter part of May would be better.
3. Prince Edward Island a great place to travel through cross over on a ferry and return to New Brunswick via an 8 k bridge. While in New Brunswick you have a choice of British or French cultures basically splitting the province in two.
4. At the top of NB you enter Quebec and I am sure most would suggest doing the Gasp Peninsula a great stretch of road funneling you down the St Lawrence seaway on your way to Quebec city and then Montreal.

I am going to stop here and if you want me to continue let me know. This could take about 10 days depending on weather.

Paul