In Sapphire, mine was probably Fortree's gym. The puzzles really annoyed me, but were fun - I hate how they're easier in Emerald. And Altaria was incredibly difficult to beat. Dragon type (loads of resistances) + Earthquake (loads of things weak to it) = pain.
That was in the days when I was a noob. Good old days.
Anyway, in Emerald, it was probably Petalburg gym. Not only the gym leader, but the other trainers were annoying to beat too. Especially when I wanted to beat all of them. Slaking annoys me to this day - just a few days ago, one nearly beat me in the Battle Dome. It OHKOed my Latios, and took 3 hits to beat, even with a max Attack Adamant Salamence and a nearly max Attack Mild Latios. Before it was KOed, it Yawned my Salamence, causing it to nearly lose to Dragon Claw Feraligator, only surviving due to some extreme luck (10 HP left and about be be KOed, it wakes up, and critical hits with Earthquake to KO Feraligatr :P).
EDIT: Oh yeah, Wattson. That was an annoying battle, with his Pokémon being annoyingly fast and outpeeding all mine. At that point, my team was something like a level 20 Combusken, a level 19 Goldeen, a level 18 Taillow, and a level 20 Skitty. Plus I KOed every wil Pokémon I saw, yet his Pokémon were still a lot higher leveled than mine :(