Synonyms for fishy are fishlike and piscine. (In the sense that you mean it anyway—fishy can also refer to something suspicious.) But, typically, those synonyms don't have as direct a connotation as fishy when it comes to taste or smell.
However: "Interesting. This vegetable has an unexpectedly piscine flavour."
As was suggested in a comment, you can change the noun from fish to the specific type of fish: salmon, trout, pickerel, etc. Although the more common use of fishy as an adjective is to denote something bad rather than good—so, I don't think that repetition is really the problem when you're talking about good qualities of fish.
You could specify a particular quality of fishy in a given context, or point out that a fish embodies a healthy "fish quality" in general.
This fish tastes salty.
This fish smells like the sea.
This is a well-cooked fish.
This fish is delicious.
This fish is fresh.
As with some of my general examples, you can assume that people know what good fish tastes like. Then you can simply say (for instance), "This fish has a strong flavour." (A version of which you already said when you asked this question.)