I still think Seismic Toss Pikachu is underrated
I know that you all seem to hate on Gyarados's babying needs, but seriously... it seeing the same tier as Pikachu and Ninetales seems kind of dumb.
ORIGINAL:
Magikarp
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.
UPDATED TO BE MORE ACCURATE:
Magikarp -
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, Fire Blast, Body Slam, and Ice Beam by TM, and also Dragon Rage and Hyper Beam through level-up.
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 has always been a fantastic Offensive type, being only resisted by Dragon, Grass, and opposing Water types. The resistances are no problem as Gyarados can hit Dragons and Grass types with Ice Beam, and opposing Water types with Thunderbolt. His Flying type gives him an immunity to ground and makes him neutral to Grass, but a Weakness to Rock and a bigger one to Electric. However, Gyarados can beat Rock types with Water moves and Electric moves are not so common in the game.
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: Gyarados can beat Voltorb and Pikachu due to their lack of a strong Electric Move, but Raichu's Thunderbolt always beats Gyarados. In Yellow, LT Surge only has Raichu, so don't bother.
Erika: At this point of the game you can get the Ice Beam TM, which if given to Gyarados can easily help him take out the gym.
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: If Gyarados has Thunderbolt he can hit the majority of her Pokemon for Super Effective Damage.
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 easily beat Golbat with either Thunderbolt or Ice Beam, but the others will be harder to take down due to the Ghosts having good Special and an immunity to Normal moves. While Gyarados can wear down her Ghosts, he must watch out for Confuse Ray hax or status.
Lance: Surf takes out Aerodactyl, while Ice Beam hits the Dragons and Thunderbolt takes out Lance's own Dragonite. In Yellow, one of his Dragonair's know Thunderbolt and his Dragonite knows Thunder.
Gary (RB): Surf takes out Rhydon, Charizard, and Arcanine. Ice Beam takes out Exeggutor, Venusaur, and Pidgeot. Thunderbolt takes out Blastoise and opposing Gyarados. While Alakazam goes down to a strong Physical Attack. Also, it is better to use Ice Beam against Pidgeot instead of Thunderbolt, as if Pidgeot survives the Thunderbolt he can Mirror Move it back to you.
Gary (Y): Surf takes out Sandslash, Ninetails, and Flareon. Ice Beam hits Exggutor while Thunderbolt hits Cloyster and Vaperon. Alazakam once again goes down to Physical Attacks, but Gyarados must watch out for Magenton and Jolteon.
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 if you allow it to have the right TMs.