After reading the post by Carillon (great ideas by the way) I was wondering.. why not add some exotic sea food? (lobster, octopus etc) which are gatherable with a net when going in deep sea? (perhaps make another option in ports to go to deep sea for fishing... you'd be sent to a map with a boat in the middle of the sea and youll get a random spawn of fishes and exotic seafood.. perhaps on the rare occasion (1%) a sea serpent would spawn.. or pirates.. although thats over the edge :p