First hearing of any part of the theme is in Underneath the Rotting Pizza. You'll hear a minor version of the first few notes of the main them from :30-:55. It starts the way the theme will start and then has a different melodic ending. This might as well be considered the "overworld theme" of the slums-- it's the music you hear when you're exploring on your own and transitioning between Wall Street and Aeris house.
The next appearance, a bit more subtle, is in Lurking in the Darkness. This has the sustained chord articulation of the final part of the main theme :09-:15 (compare with main theme below, 3:47-4:15)
Holding My Thoughts in My Heart uses the motive of the main theme over harp like arpeggiation. (:21-:45). Remember, you're just leaving Midgar when this first plays. Hearing this is literally preparing your ear to hear the main theme as significant in a moment when you step onto the overworld screen.
Then we hear the main theme for the first time once we step outside of Midgar.
On That Day Five Years Ago... This is heard for the first time when Cloud has a flashback in Nibelheim. It opens with the main theme motive, but here, as in its first appearance in Underneath the Rotting Pizza, the theme is in minor here instead of major.
Steal the Tiny Bronco uses the main theme to underscore the gun fire moments. :22-:35
When your party climbs up the crater for the first time, you hear "The Great Northern Cave." This will become both the airship theme when you're flying around and the overworld theme when you walk on the map. I don't hear any similarities between this theme and the main theme.
Who am I? Begins with the main theme over X-files-like arpeggiation. This plays when Cloud is confront Sephiroth's lies.
The Highwind Takes to the Skies also plays the main theme. Interesting to use the main theme in the airship theme-- considering that the airship theme is probably much more common to be heard in late gameplay than the theme walking around the world. Very easy to hear this theme from :14-:50.
Also, the original main theme plays for a second in the final movie. It plays as couterpoint with Tifa's theme. 1:54-2:24. The second iteration here returns to E major with a timpani roll and very much feels like a musical homecoming after playing the game and hearing the music so many times.
Did I miss any occurrences/evolutions of this theme?