Definitely the City of the Ancients. I know it's quite late in the game, as far as first visits to a location go, but the whole thing was so beautiful. The music was extremely well done "You Can Hear The Cry Of The Planet" is one of my favourite Final Fantasy pieces of music, and one of the best from FFVII, without a shadow of a doubt.

The Train Graveyard and Nibelheim as well, I suppose. "Anxious Hearts" is another one of my favourite pieces of music. Anxious Hearts is played in more than one location (it's also played in Gongaga for example).