Some notes on some of the posts so far:
According to Wikipedia, the first few seconds of the song was intentionally played at the wrong speed, as the DJ’s way of getting back at the studio manager, who had been barking orders at him all day. Unfortunately there’s no grabs of it on YouTube (I would love to hear this)
I thought it was Since I Left You? (also by The Avalanches)
I recall reading at the time it was “For One Day” by Evermore.
According to Wikipedia, it was “Never Before” by Cold Chisel.
And my own contribution:
SAFM’s first song was Sultans of Swing by Dire Straits