Fencer: Too bad about Gigamic because they have other great two-players games
But here is a great list of abstract games, always with mention of the copyright when there is one. There I found all the most interesting ones I knew and many others : http://www.di.fc.ul.pt/~jpn/gv/index.htm .
Tycho: I vote against Abalone, because though it is a very nice game, it is all too easy to build a unbreakable wall and draw in this way. Even the authors acknowledged that, and had to invent contrived etiquette rules to force the players into taking otherwise unnecessary risks.
The other ones are great suggestions, I may add some very simple and quite well-known games (all on the website I mentioned) : Pogo (good start in stacking games), Twixt, Hex (good start in connexion games), Isola.