- Vaporeon: Eevee comes from Goldenrod City and needs a Water Stone. It has solid Special Attack and bulk, but it uses up the one Eevee you are given, so you would need to breed for other Eeveelutions.
- Lapras: found in Union Cave on Fridays, and you need Surf first. It learns Ice Beam and Body Slam, but it is slow.
- Gyarados: strong Attack.
- Golduck: Psyduck is available early in Ilex Forest. It evolves late and is a useful HM user.
- Starmie: from Staryu with the Good Rod, but you need a Water Stone, which was called frustrating.
Which Pokémon is best is partly opinion. Pick based on when you want a Water type and your team.