Ask your players.
This is a strategy I adopted to great success when implementing 4e skill challenges: I might give them a set of obvious skils, but I'd also make it clear that any skill they could justify and the group considered legit would be made available. This is an at-the-table affair (not a help-me-prepare thing), and can take two expressions in the Pathfinder skill challenge paradigm you linked:
- Let the player narrate how he uses a different skill to overcome the obstacle I've given him:
- If the horse must jump a ravine, he might use Arcana to cast a minor
charm that lets the horse jump further.
- Faced with a hidden
shortcut, he could use Decipher Script to quickly understand a
scrawled notice of it in the local equivalent of hobo
sign as he
- Slightly more radical, I can give the player a chance to create the obstacle as well as the method in which he overcomes it:
- The horses begin to flag, and he uses Heal to give them their second wind.
- The enemy begins to catch up, and he uses Balance to fire off covering Parthian shots to make them back away.
By giving my players these decisions, I increased their agency and engagement in the story, and I opened up the scene to interesting and unexpected developments. It encourages creative action, and gives players a chance to shine even when their characters wouldn't be typically proficient in that particular environment.
It also reduces my prep work, but I usually have to model this behavior for new players. It's a rather radical increase in the player's narrative agency compared to common expressions of the d20 System ethos.