Honestly, granted I didn't pick Charmander, I've always found Brock to be one of the easiest. Bulbasaur and Squirtle both dominate due to their typings being super effective against Brock's Pokemon, and I always managed to take down his Pokemon without any trouble, unless I picked Charmander. Apart from Mankey there really aren't any good Pokemon to counter him with before the gym, so that always posed as a challenge. Bugsy definitely comes as a close second, simply due to how weak he was as a trainer. His only saving grace was Scyther, but it could easily be taken out with any of the Pokemon you could catch in the Union cave pretty much.
Hardest must've been either Koga, Sabrina or Whitney. Whitney has already been mentioned loads, and for good reason. And while the main trouble comes from her Miltank, due to how incredibly annoying its moveset is. And you didn't really get much of a chance to get super effective Pokemon to battle her with, since the only Fighting type I remember being available before the gym was Machop, and that was through trade at a relatively low level. Her Clefairy wasn't anything to joke about either though, with that attract combo.
Sabrina was mainly hard due to how over powered Psychic types were in the first generation, since a bug for some reason made Ghost types weak to Psychic types instead of strong I believe. And with the lack of Dark types, that'd obviously cause some trouble. So yeah, you'd have to rely on your Pokemon to just be strong enough without any super effective moves, and that's what made her so tough.
I don't think Koga was ever actually that tough, but I just always had trouble against him. I reckon it comes from most of my playthroughs of the older games being when I didn't really have a grasp on which Pokemon were what typings and how the whole type chart worked, so I never actually did too well. Nowadays I usually always bring a Ground or Psychic type with me on the team, so he isn't much trouble, but back when I mainly played the first and second generation games, he was definitely a pain.