Pokémon Red and Blue/S.S. Anne
This ship caters to some of the world's most renowned Pokémon trainers. In fact, the S.S. Anne is on its annual Pokémon cruise, where amateurs and professionals meet for a series of duels. Though not a trainer himself, the captain will give you Cut (HM 01), which will allow you to hack through the bush that blocks your path to the Vermilion City Gym.
 All aboard!
Flash your S.S. Ticket to the guard stationed at the docks, and you'll be allowed onto the massive cruise liner.
If you want to get straight down to business, take stairway C, then stairway E all the way to the Captain's cabin. But be forewarned: your rival is after the same thing, and he'll be ready for a battle when you cross paths.
The rest of the ship is completely optional, but you may find it worth your while to explore a little. An important thing to remember is that if you don't do the rival battle and see the captain first, you can go on and off at your leisure. Also, stop in the kitchen (B) and root through the trash for a Great Ball.
The Sailors in the basement may not give as much cash as the Gentlemen, but they're easy to defeat if you have strong Electric or Grass Pokémon, and defeating them gives you access to some useful items, including TM 44, which contains Rest, a skill that can be learned by any Pokémon that can use TMs. It completely fills that Pokémon's life bar, but puts it to sleep in return, so only give it to a Pokémon (maybe Jigglypuff or something) that's tough enough to survive the beat-down it's going to receive while asleep. Or, better yet, don't use it at all, since it takes several turns to do what one Super Potion could do.
NOTE: In Basement 1, Sailor #1 on the map is the one on top. On the image of the Upper Deck, the Sailor marked as #2 is not a trainer. The burly guy in the top left corner is actually Sailor #2, so don't let that surprise you.
In the very last room in the basement, if you examine the pillow on the bed, you will be awarded with a Hyper Potion!
 Before you can meet the captain... Rival Battle #4
|Stage 2 Starter
Your rival makes another appearance and demands another battle. This battle may also be the easiest of all the rival battles. While you had Routes 24, 25, and 6, plus Cerulean Gym and the rest of the S.S. Anne, to raise your Pokémon some 5-6 levels from where they were after the last fight, your rival raised his about two apiece. And he didn't even add anything.
What this means is that your strategy for all versions remains basically the same. Use Pikachu on the bird, Mankey in Yellow against the Normals, etc. However, you should have added three more Pokémon since that fight: a Grass-type (Bellsprout/Oddish), Diglett and Kadabra (by evolving Abra). As such, you can use a new strategy, assuming all your Pokémon are L22+.
- Red and Blue
Pidgeotto leads. Pikachu defeats it with a Thundershock or two, same as always. The next one is the biggest threat: his Abra evolved, meaning it can actually fight. Fearow is up to the task, fortunately; it should be faster, for starters, and it has Peck and Fury Attack running off of a high Attack hitting a low Defense. Just attack with Fearow and K.O. it quickly. Raticate is next, and while it still has the obnoxious Hyper Fang move, it has ceased to be a noteworthy threat. Use a fast, hard-hitting Pokémon (such as Kadabra, Fearow or Diglett) to beat it in one hit, before it can start being annoying. Finally, the starter also evolved, but the strategy didn't need to evolve with it. Use Fearow (Peck) or Kadabra (Confusion) on Ivysaur, Diglett (Dig) on Charmeleon, and Bellsprout/Oddish/Pikachu (Vine Whip/Absorb/Thundershock) on Wartortle.
This strategy is literally the exact same thing as in Cerulean. Use Mankey on the Normals, Ivysaur on Sandshrew, and Pikachu on Spearow.
Once you've defeated your rival, you're free to visit the seasick Captain and exchange a back rub for HM 01, which teaches Cut to just about any Pokémon. As an attack it's worthless, but when used outside of battle it lets you cut down those annoying trees that are always blocking your way.
Once you've received HM 01 your quest is complete, and the ship will sail off as soon as you set foot on dry land. So if you'd like to visit the kitchen or the other decks (to fight the other guests and crew for EXP, cash, and prizes), you might want to save the Captain for last.
Please note that the image below is not correctly labelled, and that Sailor 2 is in a different location in this area. Sailor 1 IS properly labelled. Sailor 2 is the one at the upper very front of the ship.