That mechanic for Fallen Earth sounds much like the one used in City of Heroes. Two folk could walk into a building for a quest (the same one or different ones) and get very different maps and encounters. Quite clever really, but not everyone likes overly heavy uses of instances.
Personally I would like to see persistent instances, such that the interior of a specific building would always be the same (layout, etc.) but the contents of the map could change depending on quests (super mutants, ghouls, robots, etc.) as needed. It would also be nice to see interior building design follow some kind of logical sense, as opposed to being truly random... which tends to lead to very peculiar interior spaces.
A travel map much like in the original two Fallout games is certainly a very interesting idea. I have been wondering for quite a while whether the game will be entirely open or whether it will be a collection of big zones connected by a world map. Not really sure which of these two options may be best. A worldmap could always be used as a fast travel mechanic, even if the world itself is more open.