Coup is a wonderfully simple and deep bluffing game. The rules you need to explain can fit on one side of a card; a reference sheet fits neatly on the other side, and the cards themselves have all the text you need.
Everyone gets two cards. If you run out of cards, you are out of the game. There are three actions anyone can take (take $1 from the bank, take $2 from the bank, pay $7 to make someone discard). What other actions you can take depend on the cards you claim to have in your hand. For example, the Duke can take $3 from the bank and can block anyone from taking $2 from the bank. The Assassin can make anyone discard for $3, but the Contessa blocks assassination. The other cards are the Captain and the Ambassador, which deal with stealing money, blocking theft, and trading cards. The deck has a few copies of each, depending on how many players you have.
Complexity arises because it is a bluffing game. Your hand is hidden. “I am the Duke, and I am taking $3.” You can challenge that claim. If you are right, I must discard one of my cards; if you are wrong, you must discard (and I get a new card in place of the Duke).
Not a lot of rules. LOTS of depth in terms of gameplay. It’s a simple game with 5 different cards, and my friends tell stories about showdowns and the levels of reverse psychology and game theory involved.
For this year’s Gen Con, we added a new card from an expansion, which was an interesting bit of spice. There are lots of variations on the game, but you get a surprising lot out of a few copies of five cards.