The simplest one I can remember. An article reported that play testers perceived game enemies as more intelligent when the only change made was to increase the health of the enemies... it took longer to kill them and so the players found it more challenging. They inferred the enemy was somehow smarter because it lived longer.

Some amount of random choice between behaviors is almost always perceived as intelligence. Both at the entity level and the strategic level (if the latter is appropriate to your game).

Even simply having things like randomness in the number of units that spawn in a particular place will be seen as intelligence: "wow! they new I was coming down this hallway so they sent more guards to defend!"

In an RTS we shipped a couple years ago we had only 3 tactical behaviors: direct attack, flank attack, and retreat. The AI could have multiple tactics running simultaneously. An attack followed by a retreat was often perceived as the AI trying to lure the player into it's awaiting army. Similarly different random combinations of those tactics gave the perception of "brilliant" tactical strategy: omg pincher attack!!, wow he totally waited until i left the base and then double flanked me!! how did he know that??

-me

The Thief series (well mainly 1 and 2) had very good "feels like they are smart" AI created through emergent behavoir. One was that in addition to scripted, non-mission related speechs by the NPC characters (you could overhear them having funny conversations), they where programmed with sets of possible interactions to events in their environment that could be triggered by the player or by other NPCs. So an might NPC jump at a sound, and then seeing the NPC that made it, complain about him sneaking around and scaring everyone.

The principle point was that it created the impression to the player (who was hiding in the shadows or on the otherside of the door) that the NPCs had an actual life - they where not just standing motionless until the player came into their room and activated their pre-scripted attack (as enemies often are in FPS games). The fact that many NPCs also moved around in large patrol patterns around the map built on this, and also contributed to thief having a very open ended mission structure: the player could construct original strategies for completing their objectives, rather then following a linear set of designer intended actions.

The book "AI Game Engine Programming" has a few paragraphs that you may find interesting about this. Read the section titled "Theory of Mind": http://www.charlesriver.com/resrcs/chapters/1584503440_1stChap.pdf