Brock...usually takes me a few seconds in the gym...a LOT of training my Caterpie to become a Butterfree. I try to catch the rare Caterpies on level 5 so the training is always half-way done. I HATE training them from level 2.
Misty...Hmm...Just get Pikachu and Pidgeotto up to level 23. It's really easy.
Lt. Surge...Catch a Diglett or Dugtrio. Easy.
Erika...Evolve my Charmander to Charmeleon...Easy.
Koga...Just have a high level team (Lv. 40) and he's simple.
Sabrina...Since there were no Dark types yet in the game, she was a challenge. I usually had a Blastoise, Charizard, Venasaur, Pidgeot, and a level 45 Pikachu around here so she was always pretty easy...But low level Pokemon are hard to beat her Alakazam with. And of course, my favorite Gym Leader Pokemon of all time, The FEMALE Mr. Mime!
Blaine...Let Blastoise handle it. Piece of cake.
Giovanni...Blastoise and Venasaur and he was pretty easy. (And I let Pikachu handle his Persian.
The Elite Four was easy. I just used my Pikachu, Blastoise, Charizard, Venasaur, Pidgeot, and Butterfree. (Basically the only Pokemon I caught. My PokeDex was terrible. It was like seen 110, caught 7. XD Oak wasn't happy. XD)
...PS...This was all Yellow Strategy...