More articles? Here we go:
http://ancient-architects.com/?p=591
http://ancient-architects.com/?p=610
I think with those and @GoodSelf's article, you should have enough material for quite a bunch of original puzzles. As for avoiding clichés - you can turn any cliché into an original idea by changing the puzzle's presentation (see the eyes/mirror puzzle in the first article).
Your question, "what kind of puzzle do people like", is a tricky one. First, there are those people who get annoyed by just about any kind of puzzle, but they are not your target audience anyway, so don't bother trying to appease them. For all others, I think that if a player is generally fine with puzzles and logic challenges, the exact type doesn't really matter. What's more important is to make sure that the player is aware of how things work. Include a few easy puzzles early on to explain the rules, then increase difficulty over time, but always stay true to those rules. Example: If I have solved five "pushing crate" puzzles where I could only move one crate at a time, finding that I can suddenly move two crates at once in the sixth puzzle of that sort will really annoy me, especially after wasting half an hour trying to find a solution that would work with the rules I was "taught" before.
Unless puzzles are the main kind of challenge in the game, I also tend to make the really tough puzzles optional, maybe offering a (equally tough) battle as an alternate way to progress. And it can't be said often enough - you want to test the player's creativity, not their patience. So avoid puzzles where the solution is easy to figure out, but exhausting to execute. Example: I have found out that to open a door, I have to touch the columns in the hall in the order indicated by the number of gems decorating them. Not a difficult challenge. So is it really necessary to have 37 of those columns...?