What makes a skill challenge a good one. What makes then enjoyable and fun? What ways can we make them memorable?
Making it engaging, and definitely unique, is a way to make it memorable. I'm afraid I can't be more specific; usually it's how the players handle them that make them unique. Even the most mundane of challenges are exciting and rewarding if something off-the-wall or otherwise impressive happens - especially if they roll a 1 or a 20 and you use critical successes for skillchecks.
To give an example, my current game had a player try to chat up an NPC for information, using a simple Diplomacy check. The party eventually succeeded, but the initiating character had rolled a 1, and ended up falling off his bar stool. Considering the fact that he was trying to impress the NPC - an attractive woman - it made for weeks worth of teasing for the entire party.
Alternately, you could throw in skill challenges during combat. An example is from the Tomb of Horrors supplement, where a skill challenge involves trying to disable a magical ward/device while defending yourself from an onslaught. The goal is to disable the ward and escape, not to defeat the enemies, and the experience is all the more harrowing for it.
The only other advice I could give is to make the challenge open-ended, which allows for more creativity from the players in overcoming the challenge. If they come up with off-the-wall solutions for their rolls - like using Acrobatics to wall-jump up a narrow hallway to disable a fire alarm at the top, or something equally impressive - they will remember the challenge for years.
I think a great skill challenge is one that
- Feels natural to the flow of the session.
- Feels like you've accomplished something if you succeed.
- Involves most if not all of the party.
Example when breaking into a castle:
- The rogue sneaks (Stealth) in and disables a guard (don't make him roll to disable).
- The wizard uses arcana to disable the magical wards.
- The fighter (and others) use atheletics to operate the winch to open the gate.
Don't try to create a great skill challenge. Create a great encounter. If the encounter is engaging and exciting, and if the skill challenge mechanics don't get in the way, then the players will remember it fondly.
Using the Obsidian Skill Challenge (variant) rules by Stalker0, I am able to turn all kinds of in-game situations into skill challenges, while keeping players "in the flow." They might notice me marking successes (Obsidian is N successes in three turns, not N successes before M failures) but usually they don't. I ask them what their character is doing, and tell them what skill to check. Sometimes they use a power instead. It's always fun.
One of my most successful skill challenges was using the system for mass combat. They were leading a fairly large assault on an underground city, and I designed a skill challenge with a couple of phases (assaulting the gates, leading the forces through the streets while avoiding ambushes and choke points, etc.), and threw in a couple of regular encounters throughout.
In general I think the most important thing is to keep a narrative flow and to have players thinking in terms of what they want to accomplish rather than just looking at their list of trained skills.
Here's a quick reference to an interesting blog about the topic. The fascinating aspect is the randomness feeding into the GM's narration. Expanding that a bit more and the mechanics from Echo Bazaar (not linked cause it's a web MMOG and not sure what the policies about that sort of thing are) could fit in neatly.
To summarize: Echo Bazaar has cards for random events and a rough progression of current "plot" at one's location. Each attempt at plot is a function of your skill. Using th card model from the topic along with an EBZ style plot would make for an absolutely fascinating challenge. Furthermore, as inspiration from the Red Box, don't tell players success or failure, instead narrate (and draw cards if you like) how their actions change the environment towards their goal. The other vital thing to draw from EBZ is that failure is almost always not the player's "fault." This idea of external complications (also see mouseguard) is vital as it makes players feel more empowered. An unusually high skill per level should very seldom "fail" in itself, but rather accomplishes something other than the pure objective.
As an example, consider the players doing a sneak: In a normal skill challenge you just ask them to all roll stealth and say "pass, pass, fail" etc... Using the cards idea, they would be using skills outside stealth to inform their eventual stealth roll. Using the EBZ combination with it, you'd start with a fairly standard "casing the joint" skill challenge, and every few turns and on failures, draw one of your complication cards. Thus, the players are moving through a dynamic environment where their potential options shift every time. Failure costs resources, (getting around that guard took another 10 minutes... and you only have an hour before the master of the house wakes up for breakfast). Furthermore, in this sort of thing, the players don't all have to be in the same location: the streetwise player could be narrating her efforts a few hours before hand to get rumors about the place on her turn. Narrative strongly trumps temporality in this instance, only breaking down if there's a combat.
In the Red Box, they have the dragon getting progressively angrier as the party fails skill checks. Demonstrate success and failure by environmental changes, not distracting "you made the check" statements.