Ok another mini board game review for you.
One of my recent favorite two-player head-to-head games is
Summoner Wars:

People have called Summoner Wars a "miniatures" game played with cards -- essentially players square off against each other moving around an army of units that are represented by cards. It's a little like chess except with a very heavy fantasy theme, and a huge variety of unique cards and assymetric abilities (each player has a different army with different abilities).
It's one of those games that hits a sweet spot for people who are addicted to variety because the sets come with tons of different factions you can choose from to represent your army, all of which play *very* differently.
It shares some of the same feel as Magic the Gathering, but on a spatial map. You can buy tons of additional sets of armies, and if you get really into the game you can construct your own custom decks (not for me) but this isn't a "collectible" game like Magic so there is no issue of rare and expensive cards.
I'm not a fan of overly complex and fiddly rules, and this game is definitely manageable, unlike similar games i've looked at, and it's very fast to setup and tear down.
Very fun stuff, highly recommended.