One of the best two-player boardgames I've played is a fast paced British take on American football called Bloodbowl. It's set in a fantasy world, so your team is made up of orcs, elves, ogres, and pretty much any other creature seen in The Lord of the Rings.
One of the best things about the game is that as you play more matches, your team advances. Individual players acquire new abilities, your team garners more fans, and newfound wealth provides access to wizards and other tricksey stuff. Of course, over time you also lose players to attrition, aging, and the occasional fist-through-the-face.
Although Bloodbowl is a fun game, I rarely get the chance to play it. That's what makes the discovery of FUMBBL noteworthy. It's essentially an online Bloodbowl community with it's own playable java client, sizeable user base, and complete record retention. Definitely worth a look for any fan of the iron ballet. If you do make it over there, look me up. I'm coaching under my nom de guerre LeperColony.