Going from Halifax you should stop off in New Brunswick and pay a visit to the only province without railways (okay, it sounds dumb) Prince Edward Island (it's worth a day trip to see Charlottown). Then Montreal is a must, especially the great white elephant of the Olympic stadium and it's surrounds.