I have a rough draft of a "meta-mechanic" in my head for "out-of-combat situations". Roughly an equivalent to skill-challenges, but radically, deeply different. It could be used in Exploration as well.
I'd call it "effort-based problem solving", and it would basically work like this.
- - DM explains situation, asks what players do.
- - Players explain their actions
- - DM knows how to adjudicate which of these actions are meaningful towards the problem solution (they could also be detrimental), and has guidelines to adjudicate how big/complex these actions are.
- - Based on what skills a single character employs and how many efforts does he/she make (could take lots of in-game time, or little, context is important), the DM hands to the characters that are going in the right direction some "helpful tokens". They'd work like minor items, but they'd be more similar to 4e's Alternate Rewards. The characters actually gain new abilities through their efforts.
- - Characters use these new abilities to either solve the problem, or continue in the right direction.
- - Eventually, if the problem needed very different skills (or better yet, areas of exprtise) than those the characters had, the character(s) that worked the most and better in the solution of the problem may "retrain on the fly" their theme-based features/feats/skills or whatever, to basically become a bit of experts on what they've been doing. Example: A Wizard using a lot of divination spells towards the solution of a mystery could exchange some of his "Librarian theme" benefits for "Detective theme" benefits. These changes could be temporary or not, depending on what the player and DM agree on.
- - The characters have done so many efforts and adapted so deeply towards the solution of the problem, that they arrive to the solution "naturally", possibly without even having rolled a d20 once (although it would be more of an exception than a rule).
Applied to exploration, in a long exploration session, character could have fun using their best abilities, skills, and theme-determined areas of expertise to address various challenges.
Characters who were already tailored to be good during Exploration would shine more, or maybe less since they'd be the ones that don't need to adapt.
Adaption is fun because it actually involves rebuilding (temporarily or not) a small part of the character, if enough effort/time is spent.
A trap-finder Rogue with high Wisdom could become, with a bit of trial-and-error or mentoring by the Ranger, an expert at finding curative herbs in the wild.
A Wizard with a good selection of divination spells could become a nature-themed seer able to commune with nature a bit as a druid would do.
A Ranger would use his tracking and scouting skills normally, providing the fast progressions in the task that the party needs while not-yet-adapted members struggle to be useful.
A noble fighter might use his high Strength and knowledge of tactics and battlefield to set traps and thus provide food, or he could help the ranger choose the best spots to avoid ambushes or set up them.
Possibilities are endless.
The point is: characters should feel dynamic even in their character sheet "stats". A high Strength character shouldn't just be creative in using his Athletics skill for everything, "being useful with it". He would often need to actually learn something new, in order to be useful where his athleticism is not needed. This allows for everyone to really participate in every "adventure phase", be it Exploration, Stealthy Infiltration, Political Intrigue, Information Gathering, Crime Solving and so on.
Also, i see D&D Next "DM Modules" on these "adventure phases" as adding the needed guidelines, possible retraining or acquirable "mini-themes", "effort rewards" and so on. They would encourage completely different thinking depending on the context, and each of these phases could put each player on the edge of their seats just as much as adrenaline-rich combat!
