Megaladon is a cool idea - never seen one before though...
Another idea I had was to add more cool stuff to make fishing in general less boring (and it doesn't have to be combat).
At the docks you're fishing away, then all of a sudden you get what you think is a bite. You real up something heavy and once you get it on the dock/shore/boat you and all the NPCs around notice that it's a bloated & rotted corpse. The NPCs that notice it could yell somehting like:
- "Ahhh! 'tis a gruesome sight, away with it!"
- "The situation seems quite Fishy indeed."
- "Poor bloak... dib's on his boots!"
When you double click the corpse a backpack could open with several low level items in there, maybe a treasure map, MiB, gems, and a journal you could return to another NPC for a small reward. after all items are taken from the pack the corpse disappears, or it would decay in a few minutes like a monster's corpse.