I tend to like to build setting for a game, first. I sort of see it as being a question of setting, and gameplay. Often, the setting is built around gameplay elements as in the case of a game like Zelda: The Wind Waker's dungeons. Those dungeons have lots of puzzles that require clever gameplay solutions, but tend to be structured very deliberately around those puzzles. So each room consecutively builds on the previous rooms gameplay discoveries. It's fun, but not neccesarily what I want. I'd rather have an evocative setting and work gameplay in cleverly, so that you feel like you're exploring an organic world that exists outside of your character.
That said, I have for the most part the setting for the game completed. So now it's a question of putting in gameplay elements. I have a good idea for where to head. First, I will implement basic item collection and shooting. After that I'll look at the whole "carry" mechanic, which lets you carry one large item (but you can't shoot if you are carrying).
What will you end up shooting? I'm not sure, but I bet rabbits and frogs and stuff. Maybe you will get coins for shooting them, or pelts or something?