My marginal impact on the problem is negligible. The issue only manifests itself on a very large scale. Therefore, any solution involving "just stop eating fish" needs to explain a strategy to achieve this change of behavior on a large scale. Note that simply telling people on the Internet to change is not a working strategy - for each individual, again, the impact is marginal, but individual sacrifice required is great, so most people will just shrug and go on with their lives.
Want to make a change? Sure, stop eating fish if you want to signal your commitment. But don't stop at that, because at this point you've achieved nothing. Work to have more impact. Some particular bottom-up and top-down areas I can outline that mesh nicely together:
- Work to make the idea of not eating fish more popular. If you can convince a few hundred thousand people to stop eating fish, then maybe it'll actually show up somewhere on some spreadsheet in a fishing company. Be careful not to become like PETA though - if you're too hard about the topic, people will start eating more fish just out of spite.
- Make it easier for people to stop eating fish. That involves creating and popularizing new foodstuffs that are substitute to fish, but have better ecological footprint.
- The ultimate goal: work towards making the cost of fish products correctly account for externalities. That is, making them (much) more expensive. This involves finding ways to correctly estimate the costs of ecological impact, and then convincing regulators to make fishing industry pay this cost in taxes. Also, you'll want to fight various fishing subsidies that further hide the true costs. You'll make enemies along the way. But this is something that must happen, as it is the real solution. The previous two examples I gave are only supportive to this one. Fish must get more expensive. That's the efficient way of achieving a mass change of behaviour.