If you want a really fun, complex, and good two player game that gets even better when multiplayer, try Star Realms (or Hero Realms for fantasy).

The rules are fairly simple but there are a whole lot of variations and the game is very dynamic.