Leaving out you know who so this poll can have some originality.
Read, guys. Anyway, the only gym leader I can recall ever giving me trouble is Winona with her Altaria. Whitney was a breeze with my female Quilava. Clair's Kingdra was sort of annoying but I don't remember struggling too much. Roxanne's Nosepass was difficult in my first Ruby play through, but that's more because I was a total n00b.
Oh wait, I take back my earlier statement: Norman's Slakings were awful too (though not as awful as Altaria >.> )
Brock is easy even with Charmander because all he does is use Bide all day, should have had Misty's Starmie instead.
Also who thought Roxanne's nosepass was hard?
Even then, you have nidoran (learns double kick fairly early in yellow) and mankey (in yellow and gen 3) to capture nearby. If anything Charmander starters are just introduced to the swiss army party rule earlier.
The Tales of series needs more love in America. Won't change sig until Namco gets wise. Started: 9/8/06
Misty's Starmie. It can outspeed Pikachu and Bulbasaur easily and has enough attack power to wipe them out before they even get a shot in edgewise, especially since Mt. Moon lacks enough high-EXP Pokémon to juice up on between Brock and her and thus will likely leave them underleveled.