I have been playing Machiavelli (it appears there is no English version of this game, and I can not make a link to the distributor because they automaticly link back to the main page) at work. I think what makes it such a nice game is that pure strategies won't work, and there is not much preparation required.
When playing with two players, the first player is too strong, especially in the first round, if during the first round the first player takes the "Thief" and discards the "Murderer" his advantage is huge. Therefor we adjusted the rules, such that the first player has to discard a character at random and may choose one from the remaining seven characters.
Also we discarded the rule that your buildings may not be destroyed after have build eight buildings.