I have Age of Empires III, so I love this kind of stuff. Make a native colony (some perhaps Egyptian buildings, due to Norse ones being used in a snowy enviornment) and have some units approach it. When they do, run a choice dialogue if they want to ally with the natives; if they do, then you will receive a group of natives every minute next to that post.
Age of Empires also had treasures. Put some relics around the entire map, some harder to get then others. And have each grant something special when picked up. Be sure to make them vanish when the specific hero (in our case, the explorer) gets it. Treasures can be: Gold, food, wood, specific animals that can be pets (tamed. Like: Bears, wolves, etc.). They can also consist of herding animals ie. pigs, cows, goats.
Have some savages around. Natives that cannot be recruited. Put them in places the player needs valuables, like resources and treasures. This will make gameplay much more intresing, and difficult, and realistic at that.