Totally agree with Bushido and Tony. Fallout is a non-linear game, which makes the Fallout Series. When I play linear games, I think about what I could be doing besides the tasks at hand, and I wish I was playing Fallout at some points.
Randomness adds to the non-linear game in an incredible amount. In Fallout New Vegas, I can easily make it to Vegas now because I know exactly where the safe areas, where people are that I can travel with to keep safe, where gangs are waiting to ambush me. It sucks.
But imagine if you stepped out of Doc Mitchel's house and you saw the towns people having conversations in the streets, perhaps herding some bighorners around a pen, even building things? A constantly changing world would just add to the concept even more, but it's a bit of a stretch. Really what should be focused on are how the AI works. People should have daily tasks to maintain their lives, instead of food just appearing in shops, the AI should have to take steps throughout the day to make it. A hunter was killed by a radscorpion? No meat until a new hunter is found or the possible other hunters come back with their stuff. Gun-smith was shot in the head by yours truly? Well, guess the shop keeper won't be selling guns anytime soon.
Even with that, people would be more inter-connected. I like what Obsidian did with the factions but when I can snipe a towns member right next to another citizen, and there isn't mass panic and chaos as everyone dives for cover, the AI is not intelligent. Along with that, a character should be able to sense danger, and even think about whether its attacker or its victim are appropriate to attack. Personally, I believe that a hooker with a knife should never attempt to attack a power armor clad man carrying a riot shotgun, it just doesn't make sense. Then to, AI would have to be able to buy or find things somehow. What better way then for the game to keep tabs on the items of each individual character as it needs. It could pull up what a character had and adjust anything accordingly, such as a character with a business suit on or even a player walking through Freeside would more likely be mugged then a player with messy hair and rags on. Characters with firearms at their sides would be generally left alone by thugs, but a character with nothing or a weak melee weapon would be susceptible to thievery.
Then on to the vehicles, which would add a ton more complexity to a more intelligent AI. Characters would have to get out of the way of these things if possible, if they couldn't others would have to adjust their behavior accordingly. I assure you in real-life if you hit someone with a car people either run away in fear of their lives or they try to help the other person. As Bushido said as-well, these vehicles could add to the randomness of the wasteland, caravans could be worked for, or even started by the player. I can only imagine buying a Brahmin, saddling it up and wandering across the barrenness of a new Fallout world.
I have so much more, but I still have homework to do. :D