A D&D adventure about sneaking around in the woods might easily devolve into a series of Nature checks. What Rogue Male brings to the table, and what you should bring into your skill challenges, is specificity.
Wilderness is not an undifferentiated mass of forest. There are swamps where a character might have difficulty resting, no matter what his Nature bonus. There are expanses of barren ground that you just can’t sneak across in bright daylight. A lot of skill challenge successes should actually require the PC to come up with a decent plan. Challenge PCs with specific situations, and require a plan of action, specific to the situation, before a skill roll is made. A PC who builds a raft to rest in the swamp, or hides in a wagon crossing the plain, gets to make a skill check.
If I were running a spy adventure as an extended Nature skill challenge, I’d also introduce some randomness. If I need to repeatedly come up with terrain off the top of my head, it’s likely to become stereotyped and nonspecific. I’d be better to make random charts for terrain and habitation: maybe we’ll roll up peculiar stuff, like a cabbage farm in the middle of the desert, but that will help us tell a story.