I first heard of Bowie in the 80's when he was definitely not cool. That period when guys like Rod Stewart and the Rolling Stones were putting out disco. Their older stuff was played on rock stations, and the disco stuff was shat upon.
Then somehow I got a recommendation to watch an indie film that Bowie was in / scored.
http://www.imdb.com/title/tt0082176/
Bit of an eye opener for a sheltered Midwestern kid.
I guess that's probably where I first heard "Heroes", which I only rediscovered in "Perks of a Wallflower". Excellent movie, but the first thing I did after seeing it was to find that song. Been in heavy rotation since.