For this quest you must sail to the rival island of Paros, which is located west of Naxos. An emissary named Euneas is thought to have been imprisoned there. Your task is to find him and bring him home. Sail west and dock your ship on the eastern shore of Paros. The first thing you will encounter are the ruins of the ship that was captained by Euneas. Speak with the only surviving soldier who is sat within the ruins and question him about where to begin your search. When the dialogue ends the soldier will die. You should now make your way to the south west of the island.
Once you are close enough to the rock face which is at the centre of the general quest area, use Ikaros to scout and identify the precise location of Euneas. When you reach the top of the rock face you will be able to get a good overview of the fortified marble quarry. As you drop down into the quarry from the north east, you will have two Athenian guards on your hands. They are equipped with heavy shields and long spears, so it is a good idea to use heavy attacks to weaken their defences and avoid the reach of their spears with swift evasions and retaliatory light attacks. When the guards are taken care of you will find Euneas in one of the cages to the left. Release him and make your way out of the quarry.
When you are far enough away from the quarry, the quest will update and you will be able to speak with Euneas. Question him about what he has seen. When you are done, Euneas will state that he intends to go back to Naxos and the quest will complete.