A few (relatively recent) memories:
I moved to Toronto (and Canada) in 1990. I came here several times on vacation with my parents before then, starting in 1983.
Pre-move memories include Woolworth's (I remember driving past the Woolworth's building on Bay St. where the Trump now stands) and Toby's (which used to be everywhere--there's still one in Hamilton. I also remember going to Towers and Simpson's.
At the time of my move, there were still Olive Gardens in Ontario. There used to be one in the Atrium on Bay where the Spring Rolls currently resides. (Olive Garden is still in Canada out west). Kmart and Woolco were still around, and Towers was just going out of business. Other places I remember are JJ Muggs (Eaton Centre, approximately where Joey is today) and Lime Rickey's (on Eglinton East just past Yonge). Then there was the Future's bakery--I believe the one in the Annex is still there, but they had several other locations. There also used to be a lot more Golden Griddles. Someone already has mentioned Consumer's Distributing--there used to be one at Victoria Park and Eglinton that I went to. Fairweather's was a really nice women's clothing store, unlike the tacky discount brand it's become today, and they had a large store in the Eaton Centre. And, of course, Eaton's was still Eaton's.
Another place I remember was Stitsky's, a fabric store on Bathurst St. Bought the material I made my wedding dress out of there.