Yeah, the NPC missions are really rare in buildings, and found uncommon underground. A good tip when underground is to look for "shortcut" doors, as they typically chain up, two to a dead end, culminating or converging upon secret mission rooms. Survivor missions never spawn on the surface and only spawn on the map if you buy or find a Seek Survivor scroll, and you can only find Seek Survivor on the surface missions. They neither spawn nor can be summoned at all on Ocean chunks, despite the Things To Do list at the green Ilari stone and in your pause menu explicitly instructing you to search there. Typically I find myself resorting to buying the Seek Survivor scroll sadly.
Incidently, one of the NPC "classes" is that of a scout and actually receives a +1 bonus to exploration. Unlock them and finding more NPCs (and unlocking more time zones) is a breeze.