[Dirty Floyd]

You should go to the sunken city and fish right off of the docks (you may need to go swimming to fish there). I think you can also fish in the Ruins but as I have not personally done it, I cannot confirm that location.

-Floyd