Hmmm... "A GF is involved", "mostly story, but there's a sidequest that can be done", "nothing to do with seifer", it's not Quezacotl, Ifrit, Diablos, Carbuncle, Odin, Tonberry, Pandemona, Cactuar, Doomtrain or Eden.

I say the part where Carway's guard sends you out to the Tomb of the Unknown King and you have the option of going further in and getting the Brothers.