One thing you need to capture about the old CCG is that going to dangerous places meant you were facing bigger hazards. The encounter decks as they stand right now are balanced more or less against each other. Going to Moria is no more dangerous in this game (encounter set wise) then traveling through Hollin.
I actually think you should seriously consider rethinking deck construction. Make it tougher to play certain, allies, attachments and titles without exploring certain locations.
It just depends on whether or not you are trying to recreate the whole feel of the old CCG or just the exploration aspects.