There are already plenty of good suggestions, but I'll add my grain of salt: it kind of depends where you are from.
Montreal is a nice city to visit, particularly if you are not European. The reason being that Quebec (the province) is unique in America for its European flair. Montreal being a big city has a different take on that flair and that is pretty nice.
The Old City/Port area is cobblestone small street mixed with the old industrial port to the south. It is a compelling mix.
If you do in the nicer months of the years, chances are that there will be a festival in Montreal. There is a blocked area downtown with over 7 stages for shows, absolutely worth it. It is a mini-pedestrian heaven in the city.
I have always been a fan of the markets in Montreal. Some have a great "relax and enjoy the moment" vibe. I would recommend the Marche Jean-Talon first and Atwater second.
As other have mentioned, for unique architecture, look for the Olympic Stadium, the Casino, the Biodome and the site of Expo 67. Of all of them, I'd recommend the Expo site. The juxtaposition of the site being on an island with the bridge going over is rather nice and makes for a nice walk.
Montreal is also known for its underground city, which must be true of most big northern cities. In the downtown area, you can walk underground for quite a while. There are shops, train stations and even residences. More information at: underground city.