If you are biking from Montreal to Rochester as the second leg, I am wondering why you are not choosing to bike all the way through Vermont on the 1st leg? I haven't biked over there, but have driven a lot, and the adirondak side of the lake is going to be narrow, twisting, and extremely steep, long climbs, endless roads that seem to go on forever but don't get anywhere. And no views of the adirondak mountains. The vermont side will be country roads, low traffic, rolling hills, with sweeping and gorgeous views of the lake and the mountains. The vermont side takes you through Burl (fun) and up through the Champlain Islands, which could be the highpoint of the trip.
Nothing against the NY side, I would love to bike that loop one of these days, but it is clearly harder and less obviously "good" for biking + you are going back down into NY, and could actually plan a route into and through the actual adirondaks on the way down (I think).
I assume you are getting on the Route Verte into Quebec. That should be very nice to Montreal, although a bit slow since my guess (seen it but not biked it yet) is the bike bath by Chambly along the river gets a lot of use (walkers, roller bladers, bikers) and will have a lot of cross streets. I highly recommend stopping and checking out Fort Lennox on the Richelieau River right across the border.
Sounds like a great trip though.