Yeah, there is a gamestore on St Catherine's street (you won't need to plan anything around going to St. Catherines street if you are traveling to Montreal because that is like the heart of the city). I forget the name of the store, something with the word Jeux (game/play) in it somewhere.
I went there about a year ago, and was pretty surprised with what they had. It sort of looks like a chain-store (like Microplay or GameStop), but they have a lot of classic stuff, lots with boxes too.
I picked up a boxed Cruisin Exotica (relatively rare for N64 standards), and didn't pick up a CIB Kid Kool (which I later realized I needed.