Taking place in a ruined temple gives a lot of cool possibilities.
One idea, that is somewhat complex, but should also give everyone a chance to shine:
Near the heart of the temple ruins, they find a room open to the sky, with an ancient clock - a magical sundial, of sorts - in the center of the chamber. Regardless of the position of the sun above, the sundial's time shifts erratically, as though driven by light sources not present - the sign of a long-forgotten curse.
A spectre appears upon their entrance, once a resident of the temple - and unknown to them, the cause of the curse. He warns them of the cursed sundial, but that is the only helpful advice they will get from him free of charge. Bitter about his fate and the fall of the temple, he will gladly mislead them and watch their misfortune... unless they can appeal to his better nature and convince him to let his hatred go.
As the cursed sundial turns, dangers assault the players from throughout the room - phantoms from the past, traps unleashed from a time when the temple was whole. Displaced from time, these are not foes the PCs can defeat directly - the only way to make the room safe is to break the curse and let the restless spirit know the gift of final peace.
Complexity
While the skill challenge sounds complicated, the framework for the system lets you condense everything into one pool of skill checks, rather than have to deal with any single element as a whole. The closer the PCs get to victory, the more effective each challenge might be - though the closer they get to failure, the more catastrophic one failure could be.
This would likely want to be an especially complex challenge, allowing a lot of interaction before success or failure. (Maybe 8 successes vs 4 failures.)
A time limit could be put in place for this challenge - when the sundial reaches a certain time of day, the curse might fully activate. If doing so, one could change the success/failure system - instead of failing after a certain number of failures, each failure could instead subtract one success. Complete failure would only come if they did not achieve the required number of successes before time runs out.
Or this could be let out, and they can work on the challenge until they fail in the normal fashion.
Skill Use
PCs can use a variety of skills in this challenge:
-Intelligent characters can us various knowledge skills (History, Religion, Arcana, etc) to gain insight into the nature and origin of the curse.
-Social characters can speak with the spectre, and try and learn what terrible wrong caused this - and convince it to let go of the past. If they can do so, it can tell them more about the curse, thus letting them figure out how to defeat it. Doing so gives the added bonus that the spectre will redeem itself through this process, and when they break the curse, it is able to rest at peace - and the PCs are rewarded with extra treasure for achieving this.
-Physical characters can try and make the room safe for the others to operate within, trying to lure the dangers in the room off to the side, or to block off the phantom traps displaced in time.
-Insightful characters might notice runes or inscriptions that can help other PCs figure out ways to defeat the curse, or they might be able to draw insight into the nature of the spectre. Perception and insight might not directly give success or failure, but instead give bonuses on rolls being made by other PCs.
Victory or Defeat
Success results in the removal of the curse - the sundial now functions again in the normal fashion, and the room has once more been restored to its correct moment in time. You could have a variety of rewards for this:
-It opens the way to a hidden chamber with treasure.
-It grants the PCs a blessing from the forgotten gods of the temple, restoring healing surges or providing some other benefit.
-It opens the passage into the heart temple. Without this, they must force their way through or take a longer, more dangerous route, which would give their enemy time to prepare.
-The spectre might give them advice about the foes in the temple's center. Or, if they managed to cleanse the spectre's hate, it might even reward them with a special treasure for doing so.
Defeat results in the curse remaining intact - however, they might have damaged it enough to temporarily disable it, allowing them to proceed despite their failure. This will still have consequences, however:
-The spectre might become enraged at their meddling, or driven mad by the curse, and either attack the PCs directly, or join in the next encounter. A Phane, with its level lowered to 21 or so, might make for a good solo fight, and an appropriate figure given the temporal aspects of the curse.
-The curse might inflict the PCs as the enter the next combat - buffs might expire earlier than they should, or enemies might be suddenly moving at greater speeds than expected.
-The curse might savage the PCs one final time before expiring, or might unnaturally age them, costing them healing surges.
Conclusion
Anyway! This might be a more complicated challenge than you want to run, but you said you were looking for something interesting, and this is one that would give all types of characters a chance to involve themselves.
One thing to keep in mind (regardless of whether you use this challenge or not) is that skill challenges work best when they are handled in a very freeform challenge - your group might ignore the spectre entirely, and simply puzzle out through magical knowledge how to break the curse. Or they might have no such knowledge, and focus on bringing peace to the spectre. Or they might simply deface runes and break traps until the curse expends itself. While it is likely they will involve all manner of different elements, be ready to deal with things as you go - there is rarely one direct way to overcome the challenge, and making it exciting and interesting involves coming up with appropriate results for any given success or failure.
