Shameless necro:
If an actual sea is too much, the local waters should at least be made more interesting. What if the lakes had natural residents that swam around like the land-based animals run on land? I have two specific mythical examples that could even be made to work while being abstracted away as an extremely rare fishing encounter.
http://en.wikipedia.org/wiki/VodyanoyTo make boat travel a little bit less safe, a mythical river spirit can sometimes pop up and attack you. If it wins, you're knocked out and lose some of your HHP, but are left alone, unless the HHP damage is fatal. If you win, you may get an artifact ceramic cup for your trouble, drinking out of which could have some cool effects.
The player could maybe even use some of his wyrd and a few pieces of cured tobacco to perform the "fishing ritual", which would allow the player to fish anywhere; even in spots without a fish resource, by calling on a favor of the Vodyanoy/Wodnik/Wassermann/Nix.
Here's another interesting creature:
"Russian fairy tales, on the other hand, also tell about an old wise pike that can fulfil wishes of the one who catches it, if its catcher releases it back into its habitat.
In the beginning of Boris and Arkady Strugatsky Monday Begins on Saturday a wise centuries-old pike appears in the story when main character Sasha arrives at Baba Yaga's house in Solovets." (
http://en.wikipedia.org/wiki/Esox )
A bar of wrought iron (at QL of the fish) for capturing and releasing a special and extremely rare pike? How did the game know my wishes!!?