Available Now:
Corphish from Apophyll Beach can be a pretty good option, since it hits very hard with Adaptability + Water STAB + Dark STAB.
Palpitoad, Wooper, and Shellos from Azurine Island are fairly bulky and decent offensively. However, Wooper line is the only one of the three to get Earthquake naturally, and the Earthquake TM isn't available yet, while Seismitoad can get some cool moves like Drain Punch from level up.
Available Later:
Skrelp can be found by fishing with the Super Rod in Coral Ward, which you'll get very soon, and while it evolves into a non-Water type, it hits very hard with just Sludge Wave, Dragon Pulse, and Hydro Pump + Adaptability.
You can find a Eevee in Chyrsolia Railnet, and Vaporeon is a very nice Pokemon being very bulky and strong at the same time. Although, you'll have to breed if you choose this, since you want to use a Glaceon as well.
You can revive Kabuto, Omanyte, and Tirtouga in Spinel Museum, and each of them are pretty strong in their own way.
Clauncher with Mega Launcher and moves boosted by that hits pretty hard, as well.
Piplup from 7th Street doesn't have a great level up movepool, but it does have nice stats and a great typing, which is a plus.
These Pokemon are up to the ninth badge, as after that, if you progress further, you'll be locked out of the city and won't be able to get them until you finish the stuff in the area you're stuck in. There's some pretty good Water types from that point on, as well, like Spheal, Horsea, Totodile, Lapras, and Feebas, but those would be late game.