Well-used, a skill challenge is a dynamic, evolving scenario where there is a goal, but no set path to reach it. Each effort, each "move" on the players' part, changes the state of play. Not just for good or for ill, either; it should actually move the conflict to something new or different. I've often used a chase scene as an example (where one person's failed Athletics check puts the next person in a tight spot, or one person's wildly successful Perception check allows the next person to get a juicy opportunity they wouldn't have had otherwise), but we can do social challenges just as easily. For example:
Party is comprised of a high-Cha Paladin (good Diplomacy and Religion, but low Wis, poor Insight), clever and perceptive Wizard (high Wis/Insight/Perception), smooth-talking Rogue (Deception, Streetwise, high Cha), and "high society" socially awkward but good-hearted Barbarian (great bonuses to Intimidate and not much else).
Challenge: Convince the Grand Duchess to aid the war effort against the "Gilded Alliance," which is actually controlled by the Cult of Tiamat. Party rolls initiative--not knowing that the Baron (who is secretly a Tiamat-worshipper) and the Countess (who hates the Cult, but mistakenly believes all of this is rumor-mongering). Order is Rogue, Baron, Paladin, Countess, Barbarian, Wizard.
As a social challenge, Cha and Wis skills are generally favorable, and it's reasonable that some Int skills will probably come up, but the player should justify it. Diplomacy, Deception, and Insight are pretty much shoe-ins. Skills driven by physical ability scores will require a good plan to make any sense at all--not that they can't be used, but certainly their uses are limited.
Rogue had expected (hoped) Paladin could go first, as that would let her dress up his truths with useful lies. However, she instead decides to speak a full truth for once, but instead of speaking to noble concerns, she speaks of the fears of the common person: Streetwise. An unorthodox approach, but one with potential, as the Duchess cares rather a lot about being seen as a worthy successor to her illustrious father. Roll fails...but literally by only 1 point!
The Duchess is now confused; her advisors (paid off by the Baron) have told her that the commonfolk are against any kind of warfare, but such a brazen and easily-defeated lie makes no sense. She's skeptical, and leaning against working with the party. The Baron swiftly responds: "My Lady, I believe this, ahem, adventurer has simply fallen prey to the...wrong sort manipulating her. Adventurers often must work with those in society who struggle or are not content with their lot, as some few always will be even in a just society like ours, and thus hear complaints that are not representative of the people."
Sensing an opportunity, the Paladin jumps onto this with zeal. Diplomacy, and spending a utility power to juice the roll. Flying colors. "Your Grace, I know that you may not necessarily trust the word of one whom you know little of and whose work takes her to dark places, but you know my tale; I have served the Knights of the Platinum Shield my whole life, having been raised as an orphan within its halls. I, personally, vouch for the word of my colleague; the commonfolk are as riled as she says." The Duchess is now truly concerned--she knows the Knights' reputation, and this particular knight's honor is beyond reproach, which implies that her court has been infiltrated. She chooses her next words carefully: "Be that as it may, it is one thing to hold concerns for the future, and quite another to hold the resolve to fight, or even to die, on the potential hope that it might change. What say you, Countess?"
"Your Grace, I have never been friend to war, nor yet do I give quarter to those who would sully our land and hollow out Your rule. But I have seen no evidence that such rapscallions and scoundrels are afoot, and it is the height of foolish aggression to commit soldiers on the basis of nothing more than one man's honor--not that I mean to besmirch you, Ser knight, but even the most honest heart may be deceived, by another or by its own zeal."
Barbarian fumbles. Fancy words aren't her forte. She's barely even keeping up with the conversation, but she knows how important it is. So she speaks plainly: "I am not of your people. But this I know: the dark ones are already here. I have slain some, and given the rest to your...'law men.' I don't remember numbers. But I know Book-Friend does." Aid Another, passes easily. The Countess initially looks skeptical, but softens as the Barbarian spekas. "There is something to be said for honest words spoken without artifice. I know we, as nobles and royalty, do not always see all that is true. Tell me, 'Book-Friend,' what numbers have you to show?"
The Wizard smiles, and pulls out his journal--the one he's take great care to roleplay writing in after every engagement or transaction. "Why, my Lady, it would be my pleasure to document in detail the goings-on I and my companions have faced. You see, in addition to my research, I act as coin-counter and quartermaster for our humble outfit, so it behooves me to keep precise records. Quite useful, I have found, for ensuring proper payment for services rendered. As you can see, we have dealt with not less than three-and-forty cultists just in the capital in the last three weeks alone! And amongst their papers, I found this document indicating locations within your demesne which had not yet had cells placed...you may find that particularly enlightening." History check, +2 from Aid Another, another +2 from the player exploiting past roleplay for excellent effect. And it's a crit, to boot!
Etc. as things go along. I imagine this would be a relatively high complexity challenge, since getting the Duchess on board would be a major victory for the PCs, while failing to convince her (so long as they don't crash and burn!) would merely be a setback, so long as they don't let her get assassinated or usurped before she gets a chance to change her mind.
