When I was a game design student, I learnt that mechanics are more important that anything else. Studios where I was working told me the same. And they're wright, because thinking about the story first doesn't provide you a game, and it may even complicate things, because you will have to justify the story with the mechanics. When you start with mechanics, the gameplay has the priority, and it's primordial, even if your game is based on a strong story (otherwise it's a book...).
For me, even if you plan to make an adventure games with characters, strong story, etc... You have to think about mechanics before anything. Think about how the player will interact with the characters, items, etc. You say you want to let the player explore the area, them how he will explore it? What can we do in the first hour of gameplay? What are the controls and actions the player can do? This is the kind of question you have to think about first :)