To my mind, puzzles where the goal is to formulate questions are more interesting than those which merely require finding a distribution of liars and truth-tellers that satisfies a given set of conditions. Further, puzzles where one can't ask enough questions to find out everything (but must find some particular piece of information with certainty) are often more interesting than those where one can ask more questions.
A critical requirement for a good puzzle of this form is that it clearly delineate what questions may be asked, and how different kinds of subjects will respond. While the rules may be expressed "in-universe" [e.g. if you ask the Neila an ambiguous question, he will get annoyed and shoot you, thereby denying you a chance to rescue the princess, convince her to marry you, and live happily ever on Tenalp], good rules should generally also be easy to express mathematically.
If S would be the set of possible solutions, and an entity which is asked a question may respond N ways, then for a typical puzzle is should be possible to represent any question as a collection of N subsets of S. For example, if there are three people, one of whom is a liar, a truth teller, and a devil [who may arbitrarily answer yes or no without restriction], and I ask the first if the second is a truth teller, then if the person says No the possibilities would be LTD, TDL, TLD, DLT, and DTL, and if the person says Yes the possibilities would be DLT, DTL, and LDT. Such a question would thus be [[LTD, TDL, TLD, DLT, DTL],[DLT, DTL, LDT]].
Even in puzzles with a relatively small number of possible arrangements, the number of possible questions may be quite large. There will often be restrictions on the questions one may ask [e.g. if one is asking the first person a question, any possible arrangement in which the first person is a devil must be present in both the 'yes' and 'no' sets] and some rule sets may require keeping track of state, but formulating questions as sets avoids quibbles over how to handle potentially-ambiguous questions, since for any question and arrangement, it would be clear what responses the subject would be allowed to give.