Look for someone around the Caladan seashore who might be concerned with fish getting sick.
The coordinates for the locations on the map are: 39,1; 71,23; and 43,53. Inside one of these is what you're looking for. Maybe further inside than you thought.
After that, head back to the seashore for some recreational activity. The Atreides are renowned for their skills in this activity.
Do NOT give your items to the quest NPC!!! Enter the room with both and wait a few seconds.