Depending on how big the map is, Ships can be difficult. I mean we are playing Natives who probably not know much about naviagtion on sea, but some sort of rafts would be cool i think. And with Raft's, perhaps there can be hidden pirate stashes on islands around the Mainland. so we can get a snip on technology. After a treasure hunt or something?
Perhaps tamed horses as mounts. so we can flee from those damn Pirates.
Also, i would like to see some sort of character creation. And if its possible, also females. My wife don't like playing as a guy xD.