wilderness is quite empty, farms, small villages can be hard to find without fast travel, and unknown dungeons are very hard to find period.
Since it seems
roads are a long way ahead (no pun intended), could there be alternatives?
Wanderers
NPCs/monsters walking around the land, minding their own businesses; Most of the time coming from, or heading to, some relevant place in the vicinity.
That could be seen as a smaller/achievable relative of
Random Encounters idea
Details
Each time some terrain zone is instanciated, have a small percentage of chance to instanciate NPCs or monsters in that zone. The mix could be similar to random attacks mix, or only the weaker ones, I'm not sure.
They always start walking straight ahead in some direction, peacefully; and stop when they're too far from the player and despawned, as usual:
- animals: go in any direction, but try to avoid cities/farms/temples directions. They don't pay attention to the player (or even try to walk away from you once you're detected) unless you get too close in which case they become aggressive.
- humans (not sure if villagers can be added, maybe not in 1st version): either come from or ahead toward cities/farms/temples around, if there's any. Otherwise random direction. Don't attack unless you attack (there's already random attacks in game, wanderers are just minding other businesses).
- monsters: either come from or ahead toward dungeons, if there's any. Otherwise random direction, but try to avoid cities/farms/temples directions. Switch to aggressive if they detect you, so the only way to know where they're going is to
not be detected. It should require patience and some luck, but not be impossible.