Bethesda used to work with randomly generated locations. I wish they would do that again.
However keep in mind that the result would be very different from FO3 - you would get a lot of repetition and that is very off-putting to many.
Also, in a case where the 'meat' of locations isn't affected such as what you describe:
Well I don't mean THAT much random. I mean like some new trees are there, some hills/pits are here, piece of debris and raider spawn point further away. Buildings and key things don't change.
there's no real need for randomness, is there?
Also
Actually it's one of the most open games.
It is not 'open' in the sense that, say, Daggerfall or Mount & Blade are open. It is big - still pretty much a scripted set of events, but a really large scripted set of events.