I don't recall the name of the quest, but it had me convert all the villages in a region very distant from me, and to be sure it had no city in it. When I received the quest, the region wasn't on my map, and it took I think dozens and dozens of turns of exploration and map trading to finally find it, then send guys over to convert etc. The end result was I was getting subsequent new quests which were clearly designed for era 2 or so, when I was in era 4 or 5.



Is having the target region so distant and hard to find a standard part of this quest or did I just get unlucky?

It's random. You just got unlucky. I don't remember the following steps being designed for T2 though-- it's something like give away 30+30 T3 strats next, followed by research 10 T3 techs, by necessity you're going to be in T4 before you complete that.