Engineering -
Give them pulley and mechanical advantage puzzles:
EG: They've got a lever, and the long arm is needed to raise up to get to the ledge leading out... but in order to do so, they have to pick the right guy to go up - strong enough to lash it securely, light enough to be counter balanced by the others... and then let him use a pulley pair to work it from the top.
They need strength 320 to lift the gate... but their total strength is only 60... they need a 6-fold advantage... let them work out that issue...
Chem-E (Chemical Engineering)
Give them puzzles solved by picking the right reaction. For example, "In thirst I sit, and what flame will quench my thirst?" Then give three buttons:
•.
•• ..
••• .:
Answer: •. - representing a hydrogen atom.
Draw out a labyrinth which is a molecular diagram. For example, in the polymeric repeating molecule for polybutadiene, one could have each atom be one room, each valent bond a hall... and hide something with a given clue of "Between the place where the black stuff is double met... and as they map them, each room features something associated with its atom... Water in one hydrogen room, balloons in another... Carbon rooms could have wood, soot, and tar...
Psychology
play up a few NPC's for a while... then have some avatar test their wisdom by having them come up with the correct diagnosis.
Run some riddles based in the DSM. EG: I speak in words, but nothing do I convey therewith; I talk a lot and say nothing, I see everything but react to nothing... what ails me? (Schizophrenia - note the word-salad and delusional reactions to "nothing.")
First, set up a Conflict Web. Start by setting up your factions that are involved, and why they are competing/conflicting. This is more to give you a set of motivations for any given group, leaders, etc. and allow you to simply improvise based on the group's needs/ambitions.
The Conflict Web is not static, it's a starting point. So you may easily see characters shift alliances or make temporary truces to accomplish goals.
Second, once you situate the PCs into the scenario, look at their goals, and likely problems they will face in terms of Logistics and Politics. This is effectively similar to how Apocalypse World produces "Fronts".
After each session, look at what the PCs attempted, who was affected, whether any NPC groups made major moves and figure out who is going to react and how. You can choose to update either the Conflict Web or the Logistics & Politics list, though I usually find myself only having to do serious updates after 3-6 sessions because it's relatively easy to track what happened with simple notes.
Both of these tools can scale up or down, so you can do intergalactic empire politics or the 28 guys stuck in a prison together, based on whatever fits your campaign.
Best Answer
I've successfully used the format found in "Logic Puzzle" magazines.
These are those puzzles that you solve on a grid of possibilities.
Usually they are things like work out which pet belongs to which person based on a list of statements.
These can be easily adapted to a fantasy or other setting and given a reason for needing to be worked out.
For example:
Now given some clues the players have to work out who wore which mask and favoured which drink. If you introduce the fact that we know which mask killed the mayor, then there's a reason to work things out to deduce who was wearing that mask.
For example
Given those clues we know it wasn't the Cleric that did the deed. A couple of more clues will lead us to the actual murderers identity.
It's easy to adapt the puzzles you can find online and just change the wording of the people/items and clues.
Also you could have more clues backed up to give the players, and give different amounts of experience based on the number of clues they needed to solve the puzzle.
You could integrate this into skill challenges by having skill checks to reveal the clues.