With Lapras, is it possible to obtain it as soon as you reach Celadon by buying Fresh Water and entering Saffron early, and then beating Blue in the Silph Co. building? Of course, this would mean having to beat his level 35-40 team with your underleveled team, although it probably isn't that hard. If you can do it this way, then Lapras doesn't have as far to go to catch up.
@ Naix: Red Krabby needs a mention of Body Slam, which is basically the only good attack available to it at that point that it can use well, assuming you haven't used it yet.
Nitpick, but for the Blue battle, Kingler should be able to beat Charizard too.
@ Hemp Man: The Erika entry applies only for Erika, which Yellow Ponyta did not sweep because Weepinbell paralyzed me with Stun Spore and then Wrap-trapped me to death. I think what I wrote for that match-up is perfectly accurate. However, I'll add somewhere that Erika's gym is a great source of experience for Ponyta since that's pretty important.