Staryu: - High Tier
Route 47 (Surf, 10%, Day only), Route 19, 34, 40, 47, Olivine City, Union Cave, and Cherry Grove (Fish, 3% w/ Good Rod, 30% w/ Super Rod, Night Only). Obtainable as early as the Third Badge.
Staryu is a Pokémon definitely geared towards being a Special Sweeper, with an acceptable Base 100 Sp. Attack as a Starmie, as well as a tremendous 115 Speed. Its bulk of 60 HP/85 Defence/85 Sp. Defence leaves much to be desired, but when you can outspeed an deal lots of damage, it does not tend to matter much.
As a Staryu, it is a mono-water, and becomes a Water/Psychic upon evolution. The Psychic-Type gained gives it three extra nasty weaknesses to Bug, Ghost, and Dark, alongside Electric and Grass, but also gives you a nifty Fighting and Psychic resist if needed, alongside the resistances Water already gives you.
Staryu has a so-so level-up movepool, but it has nifty moves including Recover, Camouflage, Power Gem, Hydro Pump, and Light Screen, but where Staryu really shines is through the coverage it gains from TM's. Electric, Ice, and STAB Psychic coverage as a Starmie can really set it up. It even gets the three water-based HM's in Surf, Waterfall, and Whirlpool. In the end you will probably be likely to use Surf/Hydro Pump, Thunder/Thunderbolt, Blizzard/Ice Beam, and a filler, since that is all Starmie basically needs to be effective. It should be noted that if you plan to go for Thunderbolt and Ice Beam, be prepared to shell out some time on Voltorb Flip...So unless you seriously hate Focus Blast level reliability, or you are contempt with the idea of spending hours on end at the Voltorb Flip, you are better off just shelling out 11k at the Goldenrod Department Store to buy the Blizzard and Thunder TM's. Also, no STAB Psychic coverage until after the E4 sucks a lot.
-Rival #3 (Assuming you went out of your way to get Staryu): Gastly and Zubat are winnable, Magnemite is generally a no, wins against Quilava, can win against Croconaw if you have invested in Electric Coverage, and unlikely to beat Bayleef with Ice Coverage.
-Morty: You virtually lose to Gengar as either Staryu is too fragile to withstand a Shadow Ball, or Starmie suffers from being a Psychic-Type with that Ghost weakness. The Gastly and two Haunter are winnable, especially if you have Starmie, as you can bash through them in one or two hits, and you can use Awakening to take advantage of the Sleep shenanigans one of the two Haunter provides.
-Chuck: Chuck is winnable, as with Starmie, you can plough through Primeape with Surf, and spam Thunder/bolt against Poliwrath for the win.
-Jasmine: Unless you are certain you can OHKO with Surf, keep Starmie away from the Magnemite, but Steelix can easily be handled with Starmie's STAB Surf.
-Petrel #1: Zubat and Koffing fall like flies, but beware of Raticate and its Dark Coverage.
-Ariana #1: Assuming you have evolved, all of Ariana's Pokémon have SE Coverage, but Lance teams up with you this encounter, so things tend to be easier, especially he targets Ariana.
-Pryce: Seel and Dewgong fall to Electric coverage, while STAB Surf ruins Piloswine.
-Rival #4: Golbat falls to Electric Coverage, be wary when taking on Haunter, Sneasel, and Magnemite, Quilava is easy, Feraligatr can be troublesome, but falls to Electric coverage, while Ice coverage can take care of Meganium, but STAB Petal Dance will give you troubles.
-Petrel #2: STAB Surf downs the five Koffing, and can deal a large dent in Weezing, who cannot do much back bar exploding.
-Proton #2: Golbat gets zapped, Weezing gets drowned by Surf. Luckily this Weezing does not blow up.
-Ariana #2: A troublesome encounter as Arbok can just Crunch you while Surf can only 2HKO at best with no crits, Vileplume survives an Ice Beam and can deal lots with Mega Drain, and you can take out Murkrow with Electric/Ice coverage, as long as you out-speed.
-Archer: Seems troublesome, but not really. Houndour and Houndoom falls to Surf, provided you outspeed, and Koffing is nothing special to deal with.
-Clair: Gyarados falls to Thunder/Thunderbolt, the two Dragonair fall to Blizzard/Ice Beam, and Kingdra is a bit of a challenge, as you have to rely on your Electric/Ice coverage to prevail.
-Kimono Girls: Lose to Umbreon and Jolteon, win against Flareon and Vaporeon, and Espeon is so-so.
-Rival #5: Likely to lose to Sneasel, Golbat and Kadabra are winnable, Lose to Magneton unless you hit hard enough, Haunter is shaky, then there is your Rival's starter. Beat Typhlosion, can beat Feraligatr and Meganium if you hit hard enough.
-Will: Bolt-beam coverage and Water coverage is all you need. The Xatu fall to bolt-beam, Exeggutor falls to Ice coverage if you can OHKO, Slowbro gets zapped, and Jynx cannot take repeated Surfs.
-Koga: This encounter is so much easier of you had Psychic Coverage...Ariados falls to Surf if you are strong enough, but beware Giga Drain, Venomoth also falls to Surf, with no Bug Coverage helping, Forretress can blow you up, but Surf can deal lots to it still, Muk is annoying as fuck, but Surf can wear it down. Finally, bolt-beam takes care of Crobat.
-Bruno: Proof that Starmie badly needed Psychic coverage before the E4. Hitmontop fails to do much to Starmie, likewise Hitmonlee, though Hi Jump Kick can still deal impressive damage. You lose to Hitmonchan's Thunderpunch spam, while Onix falls to Surf. Machamp can deal hefty damage with Rock Slide, but repeated Surfs will suffice.
-Karen: Murkrow and Houndoom aside, who Starmie can deal with effectively bar Sucker Punch from Murkrow, the other three really give Starmie headaches.
-Lance: The three Dragonite have a serious case of Ice coverage headaches, Gyarados falls to Electric coverage, whilst Surf drowns Charizard and Aerodactyl, though Aerodactyl has Crunch and will outspeed unless Starmie has a Choice Scarf on, so watch out there.
Staryu can be obtained pretty early, and you can get a Starmie virtually straight away, since you can get the Water Stone via the Pokéathlon Shop on Mondays, Tuesdays, and Fridays. Staryu suffers from slow growth, a low encounter rate, and has one ability (Natural Cure) that is infinitely better than the other (Illuminate). Even at a level as low as the mid-30's, Starmie can fare well against the E4 with a Choice Scarf, and there is no real "terrible" match-up before Kanto per se. In Kanto, it gains Psychic-Coverage, and can continue to shine, destroying Janine, Brock, and Blaine, and can really give Misty a run for her money. Ultimately, the idea to using Starmie is to abuse its good Sp. Attack, Speed, and its great Water/Electric/Ice coverage, and by doing exactly that, Starmie will rarely ever let you down.