| Skill challenges work best when there's a clear objective the party desires and a clear obstacle to overcome. If the obstacle is potential enemy's many parties will default to killing them.
Your best bet are things they can't fight like
Escape: Running away from flooding river, finding a way out of a hazardous maze, climb down from a burning building.
Rescue: Drag people out of burning building, stop damn from collapsing, convince king to help rebuild/feed a village.
As far as cheesing it up goes, your players know when you are entering combat right? Do you ever say "this is a combat?" No, you say "arrow wiz by your head," or "a fireball ignites in the middle of your group."
If you simply describe the situation, "there's a high cliff that extends for miles in each direction. You think you will lose a lot of time if you run around the side, but if you climb up it you might be able to chase the dragon faster. You know this dragon makes slaves of it's captives after a day or so and they will fight against you after that. Time is clearly of the essence."
"To get to the top you can use perception, dungeoneering, and nature to find the best route up and avoid obstacles, endurance to keep holding on the whole way, acrobatics if you want to use some of the hanging vines to swing up in places, and athletics. "
It also helps to explain how you will run skill challenges before your game so that your players know they will happen and how best to interact with the challenges they face. They spend a lot of time learning about how to use their characters in combat, but rarely is much time spent learning how to use actions or skills for a skill challenge. Many players may not know that you need a certain amount of successes before failures (you should be letting them know when they get each of these). It's worth talking over. | 
And yet another word from our sponsors
