A few good Pokemon you might want include
- Kingdra
This Pokemon will require some effort, but it might be worth it. Horsea is found much later in the game, around sea routes 132, 133 and 134 which is a bit of a pain, and still you will need one with a Dragon Scale in order to get it to Kingdra form. The only way to find a Dragon Scale is from wild Horsea, they have a 5% chance of holding. Overall, they are pretty rare so it might take a lot of work. It's probably worth it though, it has pretty good stats overall. This may not be your best choice though.
- Starmie
Staryu is found along the outskirts of Lilycove, and when you evolve it has great stats, with also an extra Psychic typing and even some cool Ice- and Electric-type moves here and there if you include TMs. You will need a Water Stone to evolve it though, and again Lilycove is quite a long way away.
- Gyarados
Has an atrocious attack base stat of 125, along with other decent stats. Magikarp is found in literally every water hole in Hoenn if you use an Old Rod. There are also a plethora of moves of various types it can learn if you use TMs!
- Pelipper
Pelipper's pretty decent all round, it might not be your best choice though. It's a Fly Pokemon, and it can learn Shock Wave which is the complete opposite of it's typing, literally.
- Sharpedo
It's a wonky Pokemon, dismal defense stats but great attack stats. Also doesn't learn any Water-type moves through level up. But it has a Dark-typing, and Rough Skin is a bonus.
- Wailord
It learns a plethora of moves, and Wailmer can be found in a lot of places with fishing. Also has an incredible 170 HP stat, but that's probably not the best advantage you could have.
- Milotic
Feebas will take an incredibly long time to find, and is almost impossible to find to an extent. But when you find it and evolve it it has pretty decent stats. I probably wouldn't even recommend this at all, but it's here if you're willing to take the challenge on Route 119.
- Walrein
Pretty decent stats all round, and it's got a bonus Ice-typing.
And of course, the monster...
- Magikarp
Incredible stats, can learn moves from any type, and is overall one of the best Pokemon the Pokemon company has created. I daresay it's better than it's evolution. By far the best choice you can make, I disregard everything I say before for this incredible masterpiece and blessing of a Pokemon.
Hope I helped. :)
Source: http://www.serebii.net/pokedex-rs/water.shtml and their respective Serebii pages.
