Cinema - I *think* - when I was a boy. Saw it heeeeeaps more often after that on video cassette, my Dad used to let me hire it from the local video store regularly.
I think the cinema I used to frequent most often was Waverley Gardens in Mulgrave, Victoria. My first definite memory of going to that cinema was seeing the Tim Burton Batman film in 1990, only 4 years after TF:TM, so while I don't have a specific memory of which cinema I went to, that's the most likely.