I would love a collection of these somewhere, cos I seem to be after a similar thing to the original poster. Here's a few thoughts:
1 - copy existing puzzle/board games somehow. Another DM did a brilliant minesweeper room when I was a PC. Step on a tile and it turns green, green, orange?, PILLAR OF FLAME. And then used red and black squares later on to show more and more 'mines'. You can easily have puzzles based on chess, checkers, and so on.
2 - movement puzzles. You generate a puzzle based on the idea that when something is moved out of the way, it annoyingly creates a blockage somewhere else. This can be anything from the simple 'crate-moving' puzzles where you get through a room, to a much more complex procedure where, say, some members are controlling levers while another has to pass through a pathway generated with an item.
3 - Look at this essay
Mathematical Puzzles in Fantasy Games
which has a few ideas, and this website
Braingle: Brain Teasers, Puzzles, Riddles, Trivia and Games
which has lots and lots of stuff, but only a small amount of it could be transferred.
4 - Brainteasers and riddles CAN be good. You are right about too many puzzle ideas for DnD being riddle-based. The idea of a riddle being there with the answer being "time" (the answer is usually time with these things) and the characters just saying "time" and something magically appears is far too rediculous and crowbarred in. But if you read a lot of brainteasers, you will find a lot of them start with lines like 'there is a table with 5 bottles on' or 'you come to a town where everybody lies'. OK, these things scream out "unrealistic brainteaser" but they keep the interactive experience and they're fun. As for riddles, if you find a way to integrate them, I reckon they can work. I intend on having a room with the letters of the alphabet on the floor. There will be 3 riddles throughout the course of the dungeon, each with 4 word answers, and with each one, the 4 players will stand on one of the letters of the answer each and a different door will open. The idea of some mechanism knowing they're standing there and so opening the door isn't so hard to swallow.
