Well, if you want to get some more different types of fish without making it too difficult to get the standard for quests, how about different bait items? Worms might catch salmon, feather lure might catch trout etc. No need to add a bait shop or anything. General store might sell something of the sort. Not to mention fishing rods or such.
An alternate method could be determining available fish from the labor points. At 1 labor could catch x piddly fish, at 10 slightly better added etc.
Either of these could easily be applied to other such tasks, such as hunting for instance. It generally would take a much more skilled hunter to hunt and kill a wolf or bear than it would say a rabbit or squirrel.
Could even remotely imagine skills for the outdoorsman type skills (fishing, hunting, tracking, trapping, tanning, etc)
Or you could cheat: get a good big net, and some dynamite...