One idea for an epic-level skill challenge I've always wanted to try out is this: the PCs activate a trap that sends them into a pocket dimension populated by a single glabrezu.
The glabrezu was imprisoned here for displeasing one demon prince or another. He can control the entire pocket dimension, creating whatever he desires out of it. The only thing he cannot create is a means of egress. It is a prison, after all.
Glabrezu have a typical Intelligence in the mid-20s region, while most demons have an intelligence of less than ten. Even the bigger, badder ones go no higher than 15. Essentially, glabrezu are geniuses, and with only other slavering demons for company, they rarely feel intellectually challenged. This situation is compounded by the fact that this glabrezu is particularly intelligent, and worse yet, has been imprisoned in this pocket dimension for the better part of a millenium.
He only gets a victim every hundred years so, and after so many years of this nonsense, the glabrezu has decided to try something different. He approaches the party, treating them in a friendly and civil manner... perhaps even offering them tea. He has a request: they are to engage him in an entertaining, enlightening intellectual debate. If the party wins the debate and convinces him of their argument, he will let them go. If the party fails, well... at least they provided some meager entertainment before the glabrezu had to go about the tedium of destroying them, molecule by molecule.
If the party is unable to think of a good topic for debate, the glabrezu gladly provides one. Demons are interested in the utter destruction of the universe, to plunge it into pure chaos and evil. The party (presumably) stand in opposition to this viewpoint. Essentially, they'll be arguing against the demonic philosophy... making a case for existence.
This won't be easy. The glabrezu's line of reasoning is that the universe once belonged to primordial masters like his demon princes. Therefore, the gods and mortals are usurpers. Therefore, their life is forfeit. Why shouldn't he tear reality apart? The natural world, to him, is an aberration, a wild experiment that has gone on for far too long.
Arguments relying on morality or the sanctity of life do little to sway him; he is a brilliant creature, but still an utterly evil one. More successful tactics might include suggesting that a universe populated with mortals and gods is "more interesting" than a void of blank chaos. The glabrezu might also respond to rational or philosophical arguments that the demon's goal is impossible ("darkness cannot exist without light," for instance, would sway him more than "destroying the world will kill millions of innocents").
If the party wins the challenge, the glabrezu summons a portal for the party to use. He can allow other creatures to escape his domain, but cannot escape himself. "Apparently my former master had a greater sense of irony than I originally gave him credit for," the creature will dryly remark to explain away this apparent oversight in the trap. On a failure, combat will ensue. Though normally an Elite, you might consider bumping him up to Solo to challenge the party. Or maybe give him minions that he creates out of the raw stuff of his pocket-prison, or otherwise summons. Or surround him with devious traps he's had an eternity to set up. Either way, the combat should be a huge and obvious challenge, one to be avoided. The glabrezu is quite nearly a god in this place.
If the party tries to jump the gun and pounce the glabrezu before the skill challenge is finished, the glabrezu will use his powers to evade the party until they "settle down". He might turn the entire pocket-dimension pitch-black, or bury himself beneath a mountain or pure mithril, or just stretch the prison by billions of miles, placing himself an impossible distance away from the party. His evasions make two things clear: the party won't be able to resolve this until they chat the demon up to his liking, and secondly that the glabrezu is so powerful that it may be a bad idea to blindly charge him. The glabrezu wants to enjoy himself with these victims. He so rarely gets to speak to somebody, and won't let them resort to violence until after he's grown bored with their feeble arguments for a continued existance.
If they fail the challenge, they then engage the glabrezu in combat, (when the glabrezu becomes bloodied, it realizes that the party might be strong enough to finally kill him and grant him release, and so continues fighting but does not attempt to evade them with his powers as he possibly did earlier, pre-debate). Assuming they win, you can set up another skill challenge to see if they can escape the pocket dimension. Or, if you just want to get on with it, you can have the pocket dimension collapse in on itself with the demon's death; his anguish was the metaphysical support strut holding the whole place up. Whatever you think your group would enjoy more.
Heh, obviously, that's not terribly useful to you, as you're just starting a new campaign, and you won't hit epic for quite a while (if at all). You could always scale it down and use it earlier, if you like. Still, it hopefully gives you a sense of what skill challenges can do.
Another thing I've had some success with is using skill challenges to represent mass combat. The party is on a battlefield with many allies and even more enemies. Their goal is to get to the enemy commanders and defeat them, thus winning the larger battle. To get there, run a skill challenge. Athletics and Endurance can represent physical feats, Arcana and Religion can represents feats of combat-magic, Bluff and Stealth can be used to create distractions and sneak around, etc. Additionally, anyone can expend an Encounter or Utility power for a +2 bonus to their next skill roll, or expend a Daily power for an automatic success. The catch, of course, is that the whole point of this skill challenge is to get to the enemy commanders and engage them in combat; if the players spend all their powers before getting to the commanders, they might lose the fight. But if they fail the skill challenge before getting across the battlefield, they will also be at a disadvantage (include more monsters to the final combat, or give them a 'morale penalty' to saving throws, cut away from healing surges, or otherwise do whatever you like to give the skill challenge consequence).
Anyway, just some ideas for you. Good luck!
