usually, I play with players' perceptions of certain social stigma.
For example, in a Vitorian adventure game that I ran, the main villain Walker Frost was a wealthy socialite prowler, an opium addict, and openly homosexual. The players expected him to be a pushover, both because of his social upbringing, drug addiciton, and sexual preferences.
I can still recall the look on their faces when, after being apprehended by Frost's henchmen, they came face to the face with the villain expecting some kind of dramatic scene to ensue. Instead, Frost looked at the heroes, shrugged once, and walked out of the room muttering only one order to his associates -- "Kill them".
Frost was, as they'd find out over time, the very picture of calculated ruthlessness. He didn't take uncalculated risks, he cut loose any potential liabilites with all due speed (going so far as to kill his lover when said lover failed to follow his orders in the field), and was generally an emotionless sociopath.
Not at all what the players expected. Very memorable, if only because he took evil to new heights.