Kosmos is a German game publisher that has an entire line devoted to two-player games. Many of them are excellent, and most are available in English editions; here are my picks for the best Kosmos two-player games.
Players send expeditions to five cities, each represented by a suit of cards. By playing cards in ascending order (you can skip steps, but you can never go back), players earn points -- if they create an expedition worth more than it cost to send out. Some expeditions will end up costing points.
The Greek gods Hera and Zeus are not pleased with each other, and they aren't subtle about it in this game for two players. The gameplay is somewhat reminiscent of Stratego. Sometimes the luck factor is overwhelming, but more often it's a game of tactics and subtle strategies.
Elements of Stratego, but there's much more to it than that including a distinct Lord of the Rings feel. One player controls Frodo and the good side; the other controls Lord Sauron and the evil side.
Players take turn laying down tiles that picture two flowers, sometimes the same and sometimes different. The goal is to build large plots of like flowers on your side of the board while trying to hinder your opponent from doing the same.
Some chess-like manuvering, but with a theme that involves hunters and prey (though you're never sure which is which). One player is the hunters and lumberjacks; the other is the bears and foxes. Both try to eliminate each other, and each side has different powers. A nicely balanced game.