Any Random encounter that is just one class/monster. You know the ones. The most common is a battle with nothing but Chocobos, but more rare and more infuriating is the battle with something like eight Monks or the one with eight Samurai. The Monk one is especially annoying since they're all wearing Gaia Gear and so their strategy is to surround you and spam Earth Render which hits you and heal their comrades. It's quite a sight to behold. Also any random encounter that involves Mindflayers.

The hardest story battles that are just plain difficult and not because you're prolonging it for Thievery purposes are Dorter Slums if you haven't done any random battles, battle with Gafgarion at the Execution Grounds where Time Mages are introduced and the game places you in a two against one numbers scenario, any mission that involves protecting a character but special shout out to any mission involving Rafa since she's incredibly suicidal for an A.I. Either battle with Balk; and of course, the duel with Weigraf, which might as well be the unofficial final boss.