I've tried a few times to get going as the Maori. Basically, I would sail around for ~10 turns, and if I didn't find anything I liked, I just rerolled. Some tips:
-It might be useful to immediately queue up Animal Husbandry, so that your last few turns of search, you'll already have horses visible. Although the Maori are probably one of the better options for an early religion, since you will often find a natural wonder in the search, and they also get bonus production immediately from forest/rainforest
-You often won't find a "perfect" spot, so it really depends how far down the chain you want to go. The biggest question is if you try to find a spot where you can have a few cities together, or if you try for island chains instead. It's probably more often than not that you can find a large section of land to carve out yourself, but if you can find it in time is a tough call.
-It helps to search around city-states. Often times I find city-states will cluster on the coast, but if you go inland from them, or around the corner, you can find land. But you are wasting some of their abilities settling inland.
-Try to settle away from Lautaro. You can still beat him, but given that you're probably 90% likely to get a classical Golden Age, that +10 against him is brutal. I ended up going for the Crusade belief to just break even against him.
Back to the original? To me, I think the "optimal" would be around 10 turns, enough that basically you get Code of Laws right as you're settling. Especially if you get the first envoy in a few city-states, it's very tempting to get settled earlier to bank those bonuses. But if you find the right spot, then take it. My current game I think I went about 15 turns, but settled right next to Ik-Kil, which means I managed to crank out my initial holy site next to it in like 3 turns. It can be worth delaying settling a few turns if you can find that "right" spot.