Clair's difficult, but my standard water-type in Crystal is usually either Poliwrath or Feraligatr... both of which can learn Ice Punch, which is easily buyable at Goldenrod Department Store. It works pretty well except against Kingdra, but if Ice Punch isn't a OHKO against the Dragonairs, one will probably faint my pogey in one hit with Thunderbolt. >.<
The one leader I'd say is harder is actually Jasmine, if you have no fire-type. A ground-type could do well, but if you use Graveler, it could get fainted by Iron Tail from that Steelix... and Sunny Day means water-types don't work. Of course, you can make the fight much easier by leveling up over at Mahogany/Lake of Rage/Ninja Hideout, but that means those fights are much more challenging.