First heard one of his songs on Grand Theft Auto - San Andreas. Runnin' Down a Dream on "K-DST".
After that I was introduced to his other songs through a Greatest Hits compilation. I know that's not always the recommended way into an artists work, but I remember being blown away by the quality of each and every track.
More so than any other artist, I really struggle to think of my absolute favourite Petty song. There's just so many that sit on the same equally high standard. I'll say Mary Jane for now, but ask me next week and it could change.