Navigating an AI that shouldn’t take the shortest path but the scenic route instead (e.g. fish)

I’m working on a sidescrolling game with an underwater "fish-like" AI that has some goals (interacting at various locations) and things to avoid (player).

1. Started of with a Navmesh and simple straight line navigation but since algos like A* always take the shortest path what ends up happening just doesn’t look good.

2. To solve this, I thought I could add some random area penalties to the navigation nodes (currently a grid). I generated these penalties using perlin noise, which did curve the path, but the effect is very minor, because again A* does not like to deviate from a straight line even with big penalties. If you make them too big, it’s gonna act like obstacles, which isn’t very usable either.

3. So the question is – how do I achieve something like this?

Thanks