For the earth theme, my first thought is a maze through burrowing passageways the adventurers have to crawl through. I'm looking for a burrowing creature of the elemental type that could have made the tunnels (and attack the PCs as well).
The air could be a vast empty cavern the PCs have to cross, or perhaps a trap where all the air is sucked out of the room.
If there are creatures in the dungeon, they need to be of the elemental type. Again, a subtle clue. Non-obvious elemental creatures are things like gargoyles and demons.
Also, once they have solved the four elements riddle, they could go on to a 'spririt' based boss encounter. I was also thinking fighting four elementals at the same time time could be fun and the PCs would need to get opposing elementals to hurt each other (fire steaming the water elemental, the air elemental blowing the fire one apart, etc...).
Any suggestions on fleshing this out?
Just. Wow.
I looked in this thread because I thought you were some kind of telepath and were trying to rip me off. I've been working on almost the exact same thing for my campaign, and have neared completion. Here's what I've got:
I had originally built a four-winged dungeon, each wing of which had a particular elemental theme, and was ruled over by one of four brothers, known collectively as The Elemental Four. Each brother held a key that would open a door in the middle of the dungeon (if you had all four keys) and allow the party to face the final dungeon boss.
I scrapped that idea because it seemed that it would drag on a bit, and was more trouble to design than it was worth. I have since redesigned the entire encounter-set into three encounters:
• The Challenges •
When the party first meets the Elemental Four, they are asked to overcome a series of tests, one for each of the four brothers. If they should pass all the tests, the Elemental Four will grant them unobstructed passage to their master, Vanderhaven. If the party should fail any of the tests, they will need to do battle with that brother. If the party fails multiple tests, they will fight all the brothers whose tests they failed simultaneously. So, the fight may be against just one, or all four, or any combination.
The Elemental Four do not present elementally-themed challenges, but rather, their challenges are based upon their own personalities. Lorym (Water), the youngest of the four, plays a melody on chimes of ice, and asks who can hear his music (this is a campaign-specific challenge, that would take too long to explain).
Then Korym (Fire) challenges the party to two gambits of Three Dragon Ante, and the party will have won if, at the end, Korym has less gold than he started with. Korym gets a pretty major advantage, but the party can use their skills to gain advantages of their own.
Then Dorym (Earth) challenges the party to a game of pure strategy, manifested in game terms as a skill challenge. The entire party acts as a single player in a two-player game, not unlike Chess, and must work cooperatively to defeat the more experienced Dorym. Among the options given to them is the use of Theivery to cheat. It's a moderately easy check, but failure immediately forfeits the challenge.
Finally, Sorym (Air) begins to ask seven riddles. The party answers individually, but a wrong answer removes that character from the challenge. The final riddle is a trick; Sorym heard it long ago, but hasn't been able to think of the answer. If the party even makes it to the seventh riddle, they've succeeded.
• The Battle •
Each of the Elemental Four is an Elite of one level higher than the party, so fighting one will be a cake-walk, while fighting all four will be very tough. In addition to being tough and dangerous on their own, there are six "Dual-Techs" that they can use (a la Chrono Trigger), representing each combination of two brothers. Each Dual-Tech is an Encounter Power that uses the Standard Action of two different brothers, and is devastatingly powerful. When reduced to 0 HPs, each of the brothers will surrender, and step out of the fight, waiting until its conclusion (they can be killed by attacking them further). If the party emerges victorious, the Four will present their keys to the party, allowing them access to Vanderhaven's lair.
• Vanderhaven
I had originally planned to run him much like Magus from Chrono Trigger, raising barriers that can be bypassed only by certain damage types, and occasionally casting darkness-themed spells. However, I scrapped that idea, as it meant most of the party would be sitting out if they don't have the right damage types.
Vanderhaven now opens the fight by splitting up into two copies. Each copy has its own set of actions, but otherwise shares all of Vanderhaven's stats, including HPs. Attacking any copy will damage Vanderhaven as if you had attacked him (attacking multiple copies with a burst or blast damages him only once). At 3/4, 1/2, and 1/4 HPs, Vanderhaven creates an additional copy, increasing his actions per round, and total damage output.
The lair itself is also tricky to navigate. Engraved on the stone floor is a diagram of magic (a well-known image to all magic-users in my campaign setting) consisting of a large, central circle, six smaller circles around it, and three intersecting lines. Standing in the central circle causes damage every round, but grants a bonus to attack rolls. Moving into or through a smaller circle will randomly teleport you among the six. Crossing the Ley Lines will sap healing surges (or just damage Vanderhaven). All of these features can be avoided if you go around, but that's a lot of wasted movement.
The players enter a smallish, cube-shaped room with a few passages out of it. The door, as expected, locks shut behind them once they have all entered. And that's when the gravity switches!
Roll the die to determine which side of the room has gravity. Unfortunately, this room splits off into other small rooms each with its own specific gravity. (Adjust the number of rooms for difficulty). And of course, each room is guarded by a creature with earthly ties (such as a clay golem). At the end of the maze is a large, impenetrable door with a clay jar.
If the players notice the earth theme, they may make a simple knowledge check to determine that the jar ought to be filled with a handful of dirt from each of the rooms in the maze to unlock the door.