Well, I don't know what games you are referring plus there are lots of ways to go too but I would say that these are some good choices:
A common water type Pokemon.
Decent stats. As for moveset I would give this:
Surf (since you want surf)
Brick Break/Aqua Jet
Not a bad typing. Not to bad in stats.
As for moveset:
One of my favourite water types.
Nice typing, nice stats and deep movepool.
Icy Wind/Ice Beam/Aqua Tail/Dragon Dance
Not a bad typing.
Thunder Wave/Confuse Ray
Unique typing (wow this answer is getting really long, don't worry it will end soon)
Unique typing (almost done)
I don't recommend Gyarados for Surf due to his horrible Sp.Atk
but I will give you a moveset without Surf
Good defense and Sp.Atk
Ancient Power/Rock Blast
Another Ice/Water type Pokemon
Ice Shard/Body Slam
Yet again another Ice type
Ice Fang/Ice Beam
High Defense, Now I don't recommend Surf on him but since you want a water type quickly go with Carracosta.
Sorry for the really long answer. Anyway overall I would go with either: Ludicolo, Slowbro or Whiscash, but that's my opinion.But since you just want a water type to use surf go with Carracosta since you don't have to do much to get it. In Relic Castle there is a backpacker that gives you a Cover Fossil or a Plume Fossil. Take the Cover Fossil, that gives you Tirtouga which evolves into Carracosta. Their unique typing gives them STAB over their moves and certain defenses. It's you choice to choose any of the Pokemon that I listed.
But as I said I think those are the best of them, another one you may want from the one that I listed is Lanturn.
Hope I helped!