IMO lets keep NPC's as they are. The same SPECIAL, skills, stats, weapons, but implement random encounting. For example NCR army are random around the NCR, San Francisco caravan is randomly on any like from SF->NCR, SF->BH, SF->HUB, SF->any-other-town. Muties are in some areas, but not exactly in some coords...
In one words, you know what I mean. Random encounters.