For Kanto, if we're staying RBY, probably either Brock (I normally picked Charmander or played Yellow) or Sabrina. Sabrina...man, she was hard. x_x If we're staying FR/LG, then still Brock. Most of my pokes in FR/LG had at least Bite/Crunch, plus my team was overall better suited for her. She still packs a punch though.
For Johto, no surprise...Whitney. I believe everyone else has pretty much summed up the problems.
For Hoenn, it was actually Winona. I haven't actually played through in a few years, so I'm a little fuzzy on why, but I remember that all three playthroughs, I had issues dealing with it. I specifically remember that that's what made me turn around and get a Pikachu from the Safari Zone. I hadn't been using one, since that's probably the most overused pokemon in history, but that just pushed me over the edge. She hit hard and she hit fast.
I don't really remember having any problems with the Sinnoh gyms. I blasted right through them, actually ending up about 8 levels below the average pokemon trainers' pokemon by the time I beat the 8th gym. Now, the gym leaders...that's a different story. >_< I've nearly spent 10 hours training, and still am having toruble getting through, mainly because I'm picky about when to use full restores and revives.