You know, as I'm going through them, they really aren't that hard. However, this is largely due to my type diversity. You see, I'm a master of dual-types: I train all of them, and they are all I train. So I train a considerable amount of Pokemon, seeing as I train all available dual-types. So when I come to a gym, I choose 6 Pokemon that will simply devestate them. They're rather easy because of it.
I have to go now, but I'll update this post with what I have used for each leader.
Edits:
Brock ~ Spearow , Weedle , Caterpie , Pidgey , Bulbasaur
This was the 1st Gym... so I didn't have much. The 1st 4 got slaughtered, and then Bulbasaur came and saved the day.
Misty ~ Bulbasaur , Oddish , Paras, Magikarp, Pidgey, Beedrill
Misty wasn't easy, seeing as I was still early and the game, without a VS seeker, and training a bunch of Pokemon (I had others in the box). SO I was very underleveled. But after I think 2 restarts, I won :D Leech Seed + Poisoned = win. True story.
Lt. Surge ~ Nidoqueen , Ivysaur , Paras , Nidoqueen , Gloom
LOL I killed the mess out of him. The only Pokemon that was even "in need of medical care" was Nidoqueen. Everyone else was in next to, if not, in perfect condition. I owned him. I also had a Meoth in my party to Cut in and Cut out.
Eika ~ Vileplume , Butterfree , Beedrill , Fearow , Pidgeot
Same as Lt. Surge, I had a Meoth for cut Purposes. But my actual team was pretty awesome. I had Super effective against and not very effective in defense. I totally got her, especailly since she only had 3 Pokemon.