Kenji's Guide Edit
This is probably the most repeated map of all time. It is entirely possible to spawn on top of enemy fire ships and triremes. So just get use to restarting.
Keep restarting until you find a landmass that is close, and has enough terrain for you comfortably settle out of range of enemy triremes. It is more than likely you will have to settle the opposite side of an enemy island.
Use four villagers to build your town center, while the fifth builds two houses. This allows you to start building more villagers as soon as the town center is done. Wall yourself in, focus on resources, (possibly use the uncommon adviser Councilman Onesiphorus), and age up as fast as you can.
Unless you're playing as the Celts, you can often use your siege ship to destroy or cripple the enemy that's on the same island as you, making this challenge much easier. After finding a suitable landmass, send a ship in both directions along the coast until you find the enemy base or villagers, then send your siege ship to that area. If you can't see their town center (or it's out of range), keep scouting along the coast: there is almost always a spot that your siege ship can attack the town center from. After it's destroyed, target their barracks, and then their units. If at any time you encounter enemy ships, restart. You may also need to use your starting troops to clear their remaining units, but this is usually very easy if you simply kite them into range of your triremes/galleys. You now have the island all to yourself until there are 2-3 minutes remaining, when ships carrying units from the other islands will start arriving.It's not uncommon to finish the quest in the manner shown to the right.