Frillish/Jellicent is a pretty good option for a Water-type (and Ghost-type). They are found in Virbank City and Humilau City when surfing. It has a good type combination and a good movepool, as well as handy abilities.
Starmie can also come in handy later on cos of its good Speed and Special Attack. A good Starmie moveset should consist of Surf, Psychic, Thunderbolt and Ice Beam, all obtained from TMs. You can catch Staryu on Route 13 and evolve it with a Water Stone.
I recommend these two but take your pick.