-Staryu - High Tier
: Like most late-game Water-types, Staryu can be found in Seafoam Islands, at or around level 30. However, if you're really impatient, you can use a Super Rod at Fuschia City to catch one, but keep in mind that it can only be found at level 15 by that method. Being a stone evolution Pokemon, Staryu can evolve whenever you want.
: Starmie's Speed allows it to outspeed everything in the game (except for your rival's Jolteon in Yellow, but Jolteon wins that match-up regardless) as well as giving it a formidable 22.5% critical hit ratio, while its Special makes it a solid special attacker and also giving it decent special bulk.
: Its unimpressive level-up movepool (barring the almighty Recover) is a double-edged sword; while it allows you to evolve Staryu as soon as you catch it, it also means it's largely reliant on TMs and Surf to be good. Thankfully, all it really needs is Surf and Psychic (whose competition is Mr. Mime, Jynx, and maybe Drowzee. In other words, fellow Psychic-types) to be a quality contributor. Thunderbolt and Ice Beam are just additional perks.
: From the moment you evolve it and teach it Surf (and hopefully Psychic as well), Starmie is ready to duke it out with a good amount of trainers, and it will need to beat a lot in order to completely catch up, as the rest of your team should be at least level 36, while Starmie's only level 30-32, and it takes longer for it to level up than most others. Despite being on even playing ground in terms of levels, Starmie can still easily plow through opponents, provided it can hit them super-effectively. Once it's caught up, it can wash unresisted opponents away with Surf alone, and it's also one of the few late-game Water-types that doesn't have too much difficulty with fellow Water-types (thanks, Psychic and Thunderbolt!).
: Starmie is one of a few Pokemon that have not just one, but two great STABs to use; Psychic is super-effective on a wide variety of things, and Surf allows it to absolutely flood Cinnabar and Viridian Gyms. Even Water Gun (which it should know when you catch it) can be useful for dealing with some Water-weak Pokemon, such as Rhyhorn or Growlithe, without wasting Surf's PP. Also, Grass, Electric, and Bug are all uncommon types in-game, meaning Starmie's opponents will most likely not be able to threaten it too much, thanks to Recover.
: Provided Raichu's Thunderbolt doesn't crit, Starmie has a pretty smooth time against him.
: To make a long story short, Starmie has no trouble with her if it knows Ice Beam or Psychic.
: Because you need to beat him to Surf outside of battle, you'll have to use one caught via the Super Rod, and thus have to train it up at least 20 levels to stand a chance against him. For the battle itself, Psychic destroys him in Red and Blue, and in Yellow, its performance is a bit rougher, but still doable.
: Starmie's at a stalemate against her Alakazam, as Surf and Psychic each do less than Recover heals. Your chances of victory in Yellow are slimmer, thanks to the level bump.
: Swept away by Surf.
: Persian and Nidoqueen can take a Surf, but aside from that, he's the same as Blaine.
: Lapras is the only Pokemon on her team that can deal notable damage to Starmie, but Starmie will have a lot of trouble if it doesn't know Thunderbolt.
: Considering that his entire team is weak to Starmie's STABs, not to mention the fact that none of them have good Special, this outcome should be obvious.
: Her Ghost-types have enough special bulk to take a Psychic and confuse Starmie or put it to sleep. Her other Pokemon aren't too bad.
: Starmie sweeps his team, but only if it knows both Thunderbolt and Ice Beam. The former is needed for Gyarados, while the latter OHKOes his Dragonair and Dragonite.
: How well it does depends on what you taught it, but keep in mind that it will almost never beat his Alakazam, Magneton, or Jolteon.
: Of all the late-game Water-types, Starmie stands out as quite possibly the (second) best of them, due to its great stats and wide (albeit TM dependent) movepool. While it doesn't excel from the moment you get it (not to mention it takes a while to catch up to the rest of the team), once it's caught up, it becomes a great Pokemon that's capable of beating most of the major battles by itself, given the proper support.