From Pallet Town, you can surf south to Route 21, which leads to Cinnabar Island, home of the next Pokémon Gym.
Explore Route 21
Go to Pallet Town and get into the water, then surf southward to reach Route 21.
In the grass to the right, you can catch Pidgeotto, Rattata, Raticate, Bellsprout, Weepinbell, Tangela, and others.
Surf southward, and there is a small island to the southeast where you can get a Hyper Potion.
On this island, you can battle Fisherman Wade, who has six level 42 Magikarp. You get 1680 Pokédollars and 3 Poké Balls for winning.
On the island west of that, you can battle Fisherman Ronald, who has a level 42 Seadra and a level 42 Gyarados. You get 1680 Pokédollars and 3 Poké Balls for winning.
Southwest of Ronald, you can battle Coach Trainer Pam, who has a level 44 Machoke, a level 44 Jynx, and a level 45 Kangaskhan. You get 4500 Pokédollars for winning. Afterward, you get TM35 Ice Punch.
Go southeast from that island to find an island where you can battle Roughneck Martin, who has a level 42 Raticate and a level 42 Onix. You get 1176 Pokédollars and 3 Poké Balls for winning.
West of that island, you can battle Swimmer Spencer, who has a level 42 Seel and a level 42 Seadra. You get 840 Pokédollars and 3 Poké Balls for winning.
Southeast of there, you can battle Swimmer Jack, who has a level 42 Tentacool, a level 42 Golduck, and a level 42 Tentacruel. You get 840 Pokédollars and 3 Poké Balls for winning.
Southwest of that swimmer, there is an island where you can get a Water Stone.
On that island, you can battle Fisherman Nolan, who has a level 42 Tentacruel and a level 42 Starmie. You get 1680 Pokédollars and 3 Poké Balls for winning.
Southeast of that island, there is an island where you can battle Sailor Claude, who has a level 42 Primeape and a level 42 Machoke. You get 2520 Pokédollars and 3 Poké Balls for winning.
West of that island, you can battle Swimmer Roland, who has a level 42 Starmie and a level 42 Kingler. You get 840 Pokédollars and 3 Poké Balls for winning.
Southeast of that swimmer, there is an island where you can find a hidden set of 3 Stardust, to the right of the center of the island.
Southeast of that island, you can battle swimmer Jerome, who has a level 42 Slowbro. You get 840 Pokédollars and 3 Poké Balls for winning.
Southwest of that swimmer, there is an island where you can get a PP Up.
Go south from there to reach Cinnabar Island.