From StrategyWiki, the free strategy guide and walkthrough wiki

New Pokémon Available

Red	Blue	Yellow
Catch: Tangela Fish: Staryu		none

What was once fantasy is now amazing reality. Scientists on Cinnabar Island confirm that they can, indeed, clone Pokémon from fossils! To reach Cinnabar Island, Fly to Pallet Town and Surf to the south. You'll contend with plenty of waterborne trainers along the way, so be sure to replenish your Pokémon for the journey. Once you make it back onto dry land, you'll be on Cinnabar Island, home to the mysterious Pokémon Mansion.

[edit] So many choices!

There are only two other Gym Leaders to defeat: Blair in Cinnabar, and Giovanni back in Viridian City. But your new Surf skill has opened up a couple of other new options. You can head back to Route #9 (past Cerulean City) and get yourself a powerful Zapdos in the optional Power Plant dungeon, or head south from Fuchsia to get an Articuno in Seafoam Island.

However, this walkthrough recommends that you head to Cinnabar Island first, to defeat Blair and turn your fossils into Pokémon that may aid you on your other quests. Still, the choice is your, and you can go straight to the Power Plant or Seafoam Island, and return to this page when you're ready.

Cinnabar Island is just south of Pallet Town, so Fly back there and jump in the little pond to Route #21. Blue and Red players who couldn't get a Tangela in the Safari Zone can pick one up in the grassy area directly south of Pallet Town.

1	Fisherman	980
	Seaking	LV28
	Goldeen	LV28
	Seaking	LV28
	Seaking	LV28
2	Fisherman	945
	Magikarp	LV27
	Magikarp	LV27
	Magikarp	LV27
	Magikarp	LV27
	Magikarp	LV27
3	Cue Ball	775
	Tentacool	LV31
	Tentacool	LV31
	Tentacruel	LV31
4	Swimmer	165
	Seadra	LV33
	Tentacruel	LV33
5	Fisherman	1085
	Shellder	LV31
	Cloyster	LV31
6	Fisherman	1155
	Seaking	LV33
	Goldeen	LV34
7	Swimmer	185
	Starmie	LV37
8	Swimmer	160
	Poliwhirl	LV32
	Tentacool	LV32
	Seadra	LV32
9	Swimmer	165
	Staryu	LV33
	Wartortle	LV33

Route #21 encounters

Rattata	30%	30%	30%
Raticate	15%	15%	15%
Pidgey	40%	40%	45%
Pidgeotto	10%	10%	10%
Tangela	5%	5%	N/A
Tentacool	100%	100%	100%

Route #21 Fishing

Tentacool	-	-	✓
Tentacruel	-	-	✓
Goldeen	✓	✓	-
Horsea	✓	✓	-
Shellder	✓	✓	-
Staryu	✓	✓	✓