From all the Final Dungeons I played (FF I, II, IV, VI) I think I have to choose between Kefka's Tower or Pandaemonium.

Kefka's Tower had some hard random battles, and the three statues weren't all that easily.

But Pandaemonium was even harder, because you first had to go through Jade, then through that ten floor castle and hell, I was out of ethers and stuff in no time. And all those bosses (Astaroth, Tiamat and stuff...)

So yeah, Pandaemonium.