Totodile is probably the best Water type, but if you chose a different starter, you have a few (less effective) options.
Vaporeon is received as an Eevee in Goldenrod City and gets fun moves like Blizzard. It has high Special Attack and special bulk that allow it to be reliable throughout the game. However, Eevee needs a Water Stone to evolve, which can be inconvenient; additionally, you may find another Eeveelution like Jolteon works better for your team. Training Vaporeon locks you out of Eevee's other options.
Lapras is found in Union Cave on Fridays, which means you need to time your visit and already have a Pokemon that knows Surf. It's one of the stronger options, though: Ice Beam and Body Slam by level up and Surf by HM make it well-equipped to take on many opponents. Though it has high HP, it's slow and has average attacking stats.
Gyarados isn't as good in Gen II as it is in later games due to its shallow movepool and lack of the physical/special split. That said, its high Attack makes Strength a viable attacking option, and you can give it Surf, Whirpool, and Waterfall without impacting its in-battle capabilities. It's surprisingly specially bulky... but you might want to use it in the remakes instead.
Golduck, available early as Psyduck in Ilex Forest, has workable Special Attack and can supplement its Water STAB with moves like Blizzard, Ice Punch, and Dig. It evolves fairly late (Level 33), but Golduck is a competent battler and a useful HM mule.
Starmie is available once you get the Good Rod from Olivine City and catch Staryu. Though getting a Water Stone is frustrating, Starmie is fast, powerful, and benefits from strong moves like Surf, Psychic, and Thunder. However, its method of evolution and inferiority to Kadabra make this the worst of the five choices.
I think Lapras is the best of these choices because it doesn't need to evolve, it's able to take hits, and it gets strong moves through level-up. You will need to have Surf to get to it, however, so be sure to catch a Sentret, Krabby, or Psyduck beforehand.
Lapras
- Surf (HM)
- Ice Beam (Level 36)
- Body Slam (Level 15)
- Strength (HM) / Whirlpool (HM) / Thunder (TM in the Game Corner)
