Haha, I feel you. ^^ I had a relatable experience with Bugsy(!) in my last Crystal run.
Of course, the harshness of battles depends a lot on your team's composition. And when you're not picking obvious counter choices, normal trainers (but mostly) Gym Leaders can get pretty tough! It's as frustrating as it is entertaining. A lot of people already mentioned Elesa, she often gives me trouble too. I mostly have a lot of Grass and Flying types in my team who have trouble with Emolga or Zebstrika. Cynthia can be pretty tough as well, I've experienced some clever switches from her. Another Gym Leader I feared was Morty. I remember from a long time ago, Morty got me at the point of crying in GSC with his Gengar. He kept sweeping my whole team, and even though Dream Eater isn't the most effective move to have, after you've been switching around your whole team ends up sleeping...
The hardest battle I've had recently, was one against Bugsy in Crystal. I tried to take him on with Hoppip, Bayleef and Phanpy...
Hoppip had to stall Metapod with Poisonpowder, and level up with gained experience to learn Sleep Powder. Then it had to put Kakuna to sleep, for a switch to Phanpy. Phanpy lacks Rollout (in case you've wondered why this would be difficult) and needed to take out Kakuna with Mud-Slap or Tackle. Please don't get poisoned! Then it all came down to my main problem: Scyther. Defense Curl wouldn't help me to survive its Fury Cutter. I had to switch in Bayleef, pray for Bugsy to suffer from acute retardation and poison Scyther with Poisonpowder (don't miss!), use Reflect, and try to stall turns with Phanpy. Actually, this tactic only worked if Scyther started to Quick Attack Bayleef first and misses at least one of its Fury Cutters afterwards. Due to the Poison mechanics in GSC, Scyther wouldn't get hurt after OHKOing one of my Pokémon with Fury Cutter 5. During my first try, I failed on this last crucial part. The second try RNG blessed me with a random miss and I won the battle. I saved my game thrice. xD I didn't want to tempt fate again, haha.
Love reading posts like these. Sure, a lot of the Gyms are super easy, but a lot of them, particularly in Gen 4, are actually hard. Let's look at Sinnoh, specifically Platinum:
Roark: Headbutt off Attack equal to Gyrados (125) isn't fun so early in the game, plus flinch chance. Not
hard, but nowhere near Brock easy (tho harder than Roxanne too)
Gardenia: Not THAT bad (I have literally soloed with a
Budew before, or at least beat her Roserade with it). Still though, Reflect up with Roserade out is kinda ew.
Fantina: This is
just awful. Makes your shiny new EQ TM useless, and Mismagius's 105 Special Attack Shadow Ball should not be a thing so early on in the game. While there are a few counters (Luxio/Luxray, Floatzel with Crunch, Vespiquen with Toxic) and you can kinda brute force it, it hits so many things super-effectively. Duskull with Will-o-Wisp also screws over a few of those.
Maylene: A breather boss to an extent. Her mons can take a hit but there are loads more counters to her than the last couple of Gyms.
Wake: Odds are if you go in blind you will get wrecked. Waterfall Gyrados? Ice Fang Floatzel? I mean Quagsire is easy but it has good type synergy and all. Bottom line, really good team, and Waterfall Gyrados is enough of a challenge alone.
Byron: LOL, nice break, though not braindead easy. Every starter kinda laughs at him (tho Torterra has to watch out for Steelix Ice Fang and Empoleon has to watch out for Magneton).
Candice: Surprisingly tough. Snow Cloak Double Team Froslass is scary, and the rest of her team has good coverage.
Volkner: Not too bad, mostly because most of his team is easily walled by any decent Ground type (watch out for Luxray Ice Fang though)
All of the E4 are rough because their coverage is insane. Galactic is also a threat early on with Purugly and Skunktank, and Cyrus 3 is incredibly hard. In general, the game is one of the hardest games, but for the right reasons (unlike HGSS).