Some people say cilantro tastes like soap; my wife equates it to eating dirt.
To me, it tastes fresh and herby, with a little pungency. I love it on carnitas, or mixed with white rice. Lots of other ways, too. Raw, or lightly sauteed.
As far as old, wharfy seafood - that because it's old and/or frozen. My mom used to make trout and cod like that - and I thought I didn't like fish.
I imagine it's difficult, being land-locked, but if you get out to a coast and are able to order quality, fresh, never frozen, line-caught-today seafood you'll be amazed how un-fishy it can taste.
Great. Now I want cilantro and on some fish tacos.