I think the problem that is being seen is that some people like to zoom in to different levels and at different points. Also, it is possible that the framework for "finding the lost city of awesometreasureguardedbyancientundeadhome" needs to be different from the infiltrate the castle scenario. Perhaps using some of the same skills and abilities, but in different ways. I'm starting to think that there are some very different needs these two scenarios have, and trying to make them work satisfactorily with the exact same mechanic may be unwieldy.
I believe a sort of random encounters (but not necessarily fighting, or even negotiations) could help exploration out a lot. Perhaps a skill challenge, check, special ability use, whatever, doesn't represent a single attempt, but the party's overall ability to navigate a situation. So they have to go around. And if the party goes around, roll for random encounter (gnoll ambush, a village where everyone seemed to die in their sleep, a trading caravan that makes the spine shiver, a torrential thunderstorm that may cause a flood or destroy some of the party's food).
Also important, and quite likely a module and playstyle thing, but a noncombat encounter shouldn't just be handwaved if a character has focused to make it his "thing". If you want a character who is a wilderness explorer extroardinaire, and spend your "points of awesome" in character creation on that, you should get to play it. The fighter doesn't (usually) just say "Well, I'm yay awesome, and those are just pansied guards, so they are taken care of cause I rolled a 15 on my combat check." So the wilderness guy should have dynamic special abilities that allow him to make interesting tactical choices in his arena just like combat focused characters do.
As an aside, I would like to point out that I vehemently disagree with the "everyone must be equal in all three pillars" idea. There are too many character concepts that SHOULD be worse in one of them. Make everyone useful in all three, but not equal. Perhaps I am misunderstanding the argument of balance in all three pillars, and this is exactly what it's proponents are saying as well.
Would the best possible answer be to make the core a simple, binary exploration method for those who don't want it? THEN, have a module right in the starting books that the group agrees to use or not use. Then each character can split his abilties up how he wants. Note that this approach could still work for a "3 tiers balanced" system". The essence is you just decide in the beginning on the granularity of your exploration, much like you would decide on the method of natural healing, for example.