The best, or easiest, would be Ottawa IMO. Gatineau park on the Quebec side is fantastic riding, lots of colors and accessible right from downtown.
The Eastern Township are about 1h drive or a day's ride from Montreal. Closer, you could ride the western part of the island. The Senneville part has lots of trees but overall, it's still urban (but nice). There's some nice riding west of the island around Hudson and Oka. There are lots of good spots north of MTL but I'm not familiar with routes. The "P'tit Train Du Nord" is a 200km bike trail. About 2/3 is paved.
In Mount Orford Nat'l park near Magog:
I grew up in Quebec City but that was a while back so I can't help with specific routes except going east along the St-Lawrence or the Jacques-Cartier/Portneuf bike path. The first one has two parallel roads, a high-speed boulevard with huge shoulder, perfect for speeding with a tailwind, or the old King's road, quiet with hort steep hills. Very nice scenery even without the colors. Around oct 5-10th is the best time for colors and snow geese migration at Cap Tourmente. If you continue east, you'll end up in Charlevoix, steep hills country.
The other is the Jacques-Cartier/Portneuf path. It's paved in the city and crushed stone for the rest. It starts in the downtwon area. A few pic:
One of my favorite place for fall colors is La Mauricie park north of Trois-Rivières. Highway 155 along the St-Maurice river to La Tuque is a nice ride (pic of the road/river from a hiking trail):