Redoing
Magikarp, because my original submission wasn't very impressive.
Magikarp -
Mid Tier
Availability: You can buy it almost for free (500 Poke, to be precise), but at level 5. It evolves at level 20.
Stats: As a Magikarp, it's got nothing going for it, except for okay Speed. Once it evolves, all of its stats (minus Speed) grow from pathetic to great.
Movepool: As a Magikarp, it starts out with the useless Splash, and can't properly defend itself until it grows to level 15 and learns Tackle. Once it's a Gyarados, however, it gets the more powerful Bite, and you can teach it Water Gun via the normally useless TM12. It can also learn Thunderbolt and Ice Beam by TM, and Dragon Rage at level 25.
Power: For the first 15 levels, it won't be able to beat even a Caterpie 1-on-1. After it evolves, it can occasionally take on entire Routes by itself.
Type: Water's great when you get it, but it can't use any Water-type moves when you get it. When it evolves, its weakness to Electric becomes more amplified, but it now resists Grass and gains an immunity to Ground. Its newfound weaknesses to Ice and Rock aren't too bad, because Ice is rare in-game and Rock-types are washed away by Water Gun/Surf.
Match-ups: Because of how pathetic it is as a Magikarp, all of the following are assuming it's a Gyarados.
Misty: High Attack and resistance to Water mean that Misty's Pokemon are reliably beaten; however, it's quite unlikely that you'll have evolved Magikarp by the time you fight her.
Lt. Surge: Don't bother.
Erika: Gyarados resists Grass, but don't use it against her unless you're willing to teach it Ice Beam.
Koga: Surf hits his Pokemon's weaker Special, often KOing in 2 hits.
Sabrina: Bite/Body Slam/other Normal attack squishes her fragile Psychic-types.
Blaine: Gyarados's type advantage gives it the win.
Giovanni: See Blaine.
Lorelei: Gyara's needs Thunderbolt to harm her Pokemon, but her Lapras will usually survive a hit and send a Blizzard right back at it.
Bruno: His 2 Onix are turned to rubble by (insert Water-type attack here), and Hi Jump Kick/Submission is resisted by Gyarados's Flying secondary typing.
Agatha: Gyarados can't learn any moves that are SE against any of her Pokemon, except for Golbat. Don't use it against her unless you like seeing your sea serpent get statused.
Lance: 4 of his Pokemon resist Water, but all of them (minus Gyarados) are weak to Ice. Keep in mind that all of his Pokemon know Hyper Beam, which preys on Gyarados's mediocre Defense. In Yellow, his 2 Dragonair and Dragonite know Thunderbolt/Ice Beam and Thunder+Blizzard, respectively.
Additional Comments: As shown above, Gyarados is awesome, but if you want to use it, you'll have to bear with the completely useless Magikarp for 15 long levels, due to its experience curve (Slow). Once it evolves, however, it becomes incredibly powerful and self-sufficient.
Also redoing
Lapras, because I may have overrated it a bit in my original submission.
Lapras -
Low Tier (possibly Bottom)
Availability: Given to you by a Silph Employee, at level 15.
Stats: All of Lapras's stats are okay, with the exceptions of massive HP and unappealing Speed.
Movepool: Learns Body Slam and Ice Beam by level-up, and has TM access to Thunderbolt and Psychic. It's notably the one of the few non-starter gift Pokemon to learn both Surf and Strength.
Power: Because you get it at Lv. 15, when the levels of your opponents' Pokemon are in the high 20's to low 30's, don't expect it to be winning any fights on its own.
Type: Well, it's a Water-type with STAB on Ice Beam...
Match-ups: Because you get it at the pitiful level 15, you'll definitely need to grind to acheive good results against the remaining Gym Leaders.
Erika: Lapras won't have learned Ice Beam by then unless you used up TM13, and there's no reason to put off Erika until you get Lapras in the first place.
Koga: Surf hits his Pokemon's weak Defense, and Lapras has the bulk to take a Selfdestruct.
Sabrina: Her Pokemon are trampled on by Body Slam.
Blaine: Lapras resists Fire despite being part Ice, and gets STAB on Surf.
Giovanni: His Ground-types are washed away by Surf.
Lorelei: Lapras can go toe-to-toe against her, but don't expect it to take out more than 2 of her Pokemon.
Bruno: Lapras can take out his 2 Onix and Hitmonchan any day of the week, but it's weak to Hi Jump Kick and Submission.
Agatha: Gengar's high Speed and Lapras's low Speed mean that Lapras will usually put to sleep before it can take out her first Gengar.
Lance: Ice Beam hits his Pokemon for SE damage, and has just enough bulk to survive 2 Hyper Beams.
Additional Comments: Lapras is held back by 2 things: its late joining time, and its poor level when you get it. If it came earlier, or at a more convenient level, it would be great, but alas it isn't. At least it's a good HM Slave.