In all generation 1 games, Staryu can be caught through fishing with the Super Rod in the following locations: Route 19, Route 20, Route 21, Seafoam Islands and Cinnabar Island. In Red and Blue, it can also be found in the Seafoam Islands as a cave encounter. This is changed in Yellow to be a surfing encounter and now can also be fished up in Pallet Town and Vermilion Harbour, with various degrees of rarity in across its potential locations. Water Stones can be purchased from the Celadon Department Store
Starmie... the jewel of the sea. This mysterious Starfish has been a force to be reckoned with in every generation that has come and gone. But this is generation one and Psychic-Types are king. While this powerful Water-Type may come a bit late in comparison to its Psychic-Type competition, and is slower and less powerful than Alakazam, it shines brightly due to its superior bulk and movepool. So when you fish up this dull brown starfish, rejoice, as you have gotten your hands on one of the most powerful Pokémon in Kanto.
Gym #3 - Lt. Surge (Vermilion City, Electric-type): If you've put off fighting him for this long, I question why but Starmie, if leveled to be on par with the rest of your team at this point, should easily drown both Voltorb and Pikachu with Surf without much opposition. Raichu puts up somewhat of a fight, being able to take one Surf if Starmie is at level 35, but Thunderbolt is only looking to 3HKO in response. Enjoy your Thunderbolt TM, I heard Starmie makes a pretty good user of it.
Gym #4 - Erika (Celadon City, Grass-type): Literally just click Psychic 4 times, Tangela will take two, or throw an Ice Beam in its direction and Psychic the Poison-Types, again why did you delay this so much?
Gym #5 - Koga (Fuchsia City, Poison-type): The two Koffing should be shut down with Psychic in an instant. Muk could actually be a pest through Minimize as it has barely enough bulk to stomach a Psychic and Sludge is a likely 4HKO on a level 40 Starmie, nothing potion support can't handle however. Wheezing is in a similar boat, but Self-Destruct is a 2HKO in retaliation, which makes the risk of a critical hit somewhat unappealing.
Fighting Dojo (Saffron City, Fighting-type): One word: Psychic.
Rival (Silph Co.): Starmie's insane coverage options shines here, allowing for almost total domination depending on what starter you picked. Pidgeot is 2HKO'd by either half of the boltbeam combo, with its STAB options doing around 10% to a level 42 Starmie. Growlithe does nothing here, getting washed away by Surf. Thunderbolt has a small chance to OHKO his Gyarados and Starmie is on average 3-4HKO'd by Dragon Rage. If Starmie has Ice Beam, Exeggcute is mostly irrelevant as it is a 2HKO while it lacks a damaging move, just be cautious of Hypnosis. While Alakazam is a slower affair due to its high special stat, it lacks a way to deal neutral damage, doing around 10% with Psybeam while being 3HKO'd by Surf. In regards to his starter, Charizard is effortlessly deposed of with Surf, scoring a 2HKO in comparison to Slash's 3HKO. Blastoise struggles to do anything close to relevant damage with Bite due to Dark not being a thing yet while Thunderbolt is a potential 2HKO. Lastly, Venusaur is actually somewhat threatening due to gen 1's shoddy programming as the 100% crit rate of Razor Leaf makes it a 2HKO on Starmie. However it is a Poison-Type Pokémon that is slower than Starmie, spam that TM29 and watch it fall.
Giovanni (Silph Co., Ground-type): Nidorino is blown up by Psychic, marking the climax of Starmie's supremacy over Team Rocket. Kangaskhan is not that impressive either, outside of murdering Starmie (and most things that don't resist Normal) with a critical comet punch string (requiring all five hits) and is promptly 2HKO'd by Surf. Rhyhorn... you have a Water-Type, just use Surf already. Nidoqueen cannot 4HKO Starmie with any of its options, although Body Slam's Paralysis chance might be a nuisance, but then Surf and Psychic 2HKO.
Gym #6 - Sabrina (Saffron City, Psychic-type): Starmie defeats Kadabra with comfort, 3HKOing with Surf in exchange with Psychic's 6HKO, just be careful of Disable, even if your own Psychic does slightly more than her's. The main threat posed by Mr. Mime is Light Screen as its Confusion does pitiful amounts of damage to Starmie, getting 3HKO'd by Surf without the screen, and even then it still loses. Venomoth is surprisingly resilient to a level 40 Starmie's Psychic, not being OHKO'd despite the weakness. However its main form of retaliation is Stun Spore followed by Leech Life, of which the former is more threatening. Alakazam seems scary given that Surf is only a 4HKO at equal levels, but then it reveals Psybeam and the threat goes out the window, rivaling Kadabra's damage output at a 6HKO. Psywave might do something wacky though, so be on your toes.
Gym #7 - Blaine (Cinnabar Island, Fire-type): Surf easily OHKOs both Growlithe and Ponyta before they can respond, which is nice in the case of the later due to Fire Spin and how trapping moves function in the first generation. Rapidash is able to withstand a non-critical surf from a level 45 Starmie, but struggles in terms of it's own damage output, even with Fire Spin. Arcanine is somehow less threatening, still being 2HKO'd by Surf but only being able to 4HKO with Take Down, not even having Fire Spin to restrict Starmie's assault.
Gym #8 - Giovanni (Viridian City, Ground-type): Surf obliterates Rhyhorn and Rhydon without trouble, OHKOing both before they can try anything. Dugtrio might have been threatening had it not been at level 42 due to it having a higher base speed than Starmie and the 100 power STAB Dig at its disposal, but as it stands, both this and Slash are only 4HKOs in contrast to Surf being a OHKO. Nidoqueen is 2HKO'd by either of Starmie's STAB options and the main threat it poses is the paralysis chance of Body Slam. It is a similar story with Nidoking, except that Thrash is even less threatening as it cannot paralyze.
Rival (Route 22, pre-Elite Four): If it is unevolved Starmie is slaughtering it through its STAB options (Growlithe and Rhyhorn) or 2HKOing it with Blizzard before Solarbeam can even fire once to do the same (Exeggcute). Pidgeot and Gyarados both still struggle to harm Starmie, with their best options being Quick Attack (6HKO at level 45) and Dragon Rage (Starmie can take 3) respectively. Meanwhile Thunderbolt 2HKOs both at worst. Alakazam is a slow and potentially dangerous affair due to its higher level and access to STAB Psychic, which 4HKOs despites the the resistance, matching Surf. Healing will be required if you intend to take this on due to Alakazam's higher speed stat. In terms of his starter, Charizard and Blastoise are pretty much the same as they were back in Silph Co., although styling on Charizard with Blizzard as a result of Fire not resisting Ice yet is a new option, albeit less efficient than using Surf. Avoid Venusaur however, due to its high level Psychic is only a 3HKO, while Razor Leaf has a extremely high chance to OHKO.
Elite Four Lorelei (Indigo Plateau, Ice-type):
Elite Four Bruno (Indigo Plateau, Fighting-type):
Elite Four Agatha (Indigo Plateau, Poison-type):
Elite Four Lance (Indigo Plateau, Dragon-type):
Champion Rival (Indigo Plateau):
Gym #3 - Lt. Surge (Vermilion City, Electric-type):
Staryu's Level up movepool, as with most Pokémon in this generation, is not that impressive. At the lowest level it can be when caught, Staryu will know Tackle and Water Gun. At level 22, your Pokémon will learn Harden, needless to say this should be dumped at the first chance you have to remove it. Recover at level 27 is godly, given Starmie's superior bulk over Alakazam and good it is on that, although Potions do make it a bit redundant. At Level 32, Staryu gets Swift, which is a decently powered Normal-Type move that would be okay if Starmie didn't have a good TM movepool. Minimize at level 37 can be used to make the AI's life a misery, although they have unlimited usage of their moves in this generation, so making the foe struggle to death is not happening. Next is Light Screen at Level 42, which can be useful as a team support option, and then finally Hydro Pump at level 47 is the line's strongest STAB move, although the low power points of the move may make it unappealing in comparison to Surf. Unfortunately, Starmie does not get anything through Level up, as with the majority of other Pokémon that evolve with a stone.
In terms of Technical Machines, Starmie has a decent selection to pick from. Access to Surf is nice for STAB and the common nature of Ground and Rock-Type Pokémon. Psychic with STAB is insanely powerful in generation 1, and this should go on Starmie without a moment's hesitation. As a Water-Type Pokémon, Starmie naturally gets access to Ice Beam and Blizzard, with the later being the better option due to its 90% hit rate in this generation. Rather uniquely (except not because Gyarados and Lapras also get it) Starmie has access to Electric-Type coverage in Thunderbolt and Thunder, creating the devastating Boltbeam combo. If you feel like playing more of a support role with Starmie, it has access to Thunder Wave, Toxic and Reflect while Mimic might be fun to mess around with.
Recommended Moveset: Surf, Psychic, Blizzard/Ice Beam, Thunderbolt/Random support move
Grass-Types: Starmie's main struggles come in its weakness to Electric and Grass-Type moves, with the threat of eternal critical Razor Leaf weighing down on it. As such, picking up one of the many common Grass-Type Pokémon that exist within Kanto is a benefit to its long-term survivability. Starmie in response handles Fire-Types that threaten all of them with its STAB options, can knock out Flying-Types through its coverage options and help the many part Poison-Type Pokémon with their Psychic weakness.
Ground-Types: While they share a weakness to Grass with Starmie, the starfish is able to competently deal with most Grass-Types due to their secondary Poison-Typing, leaving them vulnerable to Psychic. Starmie additionally patches up their Water weakness and low special defence in exchange for their supremacy over Electric-Types.