Magikarp, Gyarados (all three games)
Availability: The old rod is handed out by someone in Jubilife City's west gate, and can immediately be used to encounter Magikarp a few dozen steps further on Route 218. This means Magikarp can be caught before the first (DP) second (Pt) rival battle. It can be encountered at level 15, so you don't have to deal with leveling it up while its only move is splash.
Evolution: I think this factor is just as critical as stuff like typing and movepool, so I'll be describing this in future nominations and write-ups, and I hope others do too. As for Magikarp specifically, it evolves at level 20. Because Magikarp can't learn any good moves, there's no reason to delay Magikarp's evolution any longer than level 20. It only has to be a Magikarp for 5 levels, so it shouldn't be too much of a deadweight. If you let it gain some experience from every battle, then your Magikarp should become a monstrosity of a base 125 physical attack stat before battling Gardenia.
Stats: As many people know, Magikarp's stats are among the worst of all time. This forces people to do the thing that requires putting Magikarp first in the party and switching on the first turn of each battle. Upon evolution, the base physical attack stat shoots to 125, tying Gyarados with Cranidos for the highest base physical attack of all Pokemon that can reasonably be obtained before battling Gardenia. While its base speed never goes higher than 81, it can still outspeed most opponents. This, and the fact that intimidate effectively gives extra bulk, allows Gyarados to remain useful even after the Pokemon League is defeated.
Typing: Magikarp's stats and movepool prevent it from being useful in battle, so Magikarp's typing is almost irrelevant. Gyarados definitely benefits from its water type because not many notable late-game opponents resist water, and nearly half of the Elite Four's Pokemon are weak to water. Gyarados benefits defensively as well, as the water type only has two weaknesses. Gyarados's flying type doesn't help much, as it can't learn any good flying attacks. Its only useful benefit is the neutralizing of the grass weakness. While the flying type does increase vulnerability to electric, it manages to keep the weakness count at two, which is still better than most other Pokemon.
Movepool: Gyarados quickly dragon rage, which 2HKO's everything up to Maylene. Just as NPCs start surviving dragon rages, it learns two very strong moves in ice fang (super effective against 4 types) and aqua tail (powerful STAB). It learns dragon dance a bit later, so it can pull off dragon dance sweeps against several notable late-game opponents. As for HMs, Gyarados can learn rock smash, surf, strength, and waterfall. It can be made to work using only one moveslot (tackle -> bite -> dragon rage -> aqua tail -> waterfall), so Gyarados is a good HM slave. Because its two best STABs are aqua tail and waterfall, neither of which require TMs, Gyarados can get very close to its full potential without using TMs. If you don't care about saving your TMs, Gyarados can be improved by learning earthquake.
Major Battles: These are the notable opponents that Gyarados can 1v1 without overleveling, using items in-battle, or using TMs.
Gardenia: Turtwig
Jupiter (Eterna City): Zubat, Skuntank
Fantina (Pt): Duskull, Haunter, Mismagius
Barry (Hearthome City): Staravia, Ponyta, Roselia, Buizel, Grotle, Monferno, Prinplup
Maylene: Meditite, Machoke, Lucario
Barry (Pastoria City): Ponyta, Roselia, Buizel, Starly, Staravia, Grotle, Monferno, Prinplup
Wake: Gyarados, Quagsire, Floatzel
Cyrus (Celestic Town): Sneasel, Golbat, Murkrow
Fantina (DP): Drifblim, Gengar, Mismagius
Barry (Canalave City): Ponyta, Rapidash, Roselia, Roserade, Buizel, Floatzel, Staravia, Staraptor, Heracross, Grotle, Torterra, Monferno, Infernape, Prinplup, Empoleon
Byron: Bronzor, Steelix, Bastiodon
Saturn (Lake Valor): Kadabra, Golbat, Bronzor, Toxicroak
Mars (Lake Verity): Golbat, Bronzor, Purugly
Candice: Snover, Medicham, Sneasel, Piloswine, Abomasnow, Froslass
Cyrus (Veilstone City): Sneasel, Golbat, Crobat, Murkrow, Honchkrow
Saturn (Veilstone City): Kadabra, Golbat, Bronzor, Toxicroak
Mars and Jupiter: both Bronzors, both Golbats, Purugly, Skuntank
Cyrus (Spear Pillar): Honchkrow, Gyarados, Crobat, Weavile
Cyrus (Distortion World): Houndoom, Crobat, Gyarados, Honchkrow, Weavile
Barry (Pokemon League): Staraptor, Rapidash, Roserade, Floatzel, Heracross, Snorlax, Torterra, Infernape, Empoleon
Aaron: Beautifly, Dustox, Yanmega, Scizor, Heracross, Vespiquen, Drapion
Bertha: Quagsire, Whiscash, Sudowoodo, Golem, Rhyperior, Hippowdon
Flint: Houndoom, Flareon, Lopunny, Steelix, Drifblim, Rapidash, Infernape
Lucian: Espeon, Gallade, Girafarig, Medicham, Alakazam, Bronzong
Cynthia: Spiritomb, Roserade, Gastrodon, Lucario, Milotic, Garchomp
In other words, everything that knows no electric attacks (and lots of opponents that do) become positive matchups as soon as Gyarados learns dragon rage.
Additional Comments: While it is true that Magikarp is mostly a deadweight until it evolves and learns dragon rage, it can defeat almost everything once it does. I think Gyarados's stats and movepool are far more than enough to make up for its initial uselessness. Gyarados's ability, intimidate, only makes it more bulky and gives more chances to defeat the opponent. Due to the high-level encounter, relatively early evolution, good offensive and defensive typing, good ability, great movepool that includes dragon rage, aqua tail, and several HM moves, and most importantly, stellar stats, I nominate
Magikarp for S tier in all three games.