When I found out that Zidane was
Spoiler:
originally from another world
the first time I played through. Maybe that's just me.

As for battles? The first time I went down into the Lunar Subterrain. Once I got to the part where they started throwing mini-bosses left and right at you, I was saying "you gotta be kidding me! Another one of these things?" Apparently I was completely unprepared for that dungeon and never completed it until I got the DS version.

Oh, and encountering Tonberry's for the first time (I think it was in VI). You can imagine what I yelled when I encountered them in VII.