My mom and I used to always play a game called Two Can Play, which was kinda like competitive Freecell. Needless to say, I cannot find a link to the rules.
War, for the heavy strategic elements.
Dominion is a really fun game that can be played with two.
Another vote for Casino. Cribbage and Golf are two other favorite two handed games.
Cribbage is my favorite beers-and-cards two-hander played with a standard deck of cards. There’s enough skill in it that the better player will beat the weaker in the long run, but enough short-term variance and luck to make the game interesting. I’d put it comparatively with backgammon for its balance of skill and luck. (To give you an idea, I have an iPhone cribbage app, and my win percentage is 81.25%. I would rank the AI as what you might expect from a beginner or advanced beginner. On my Hoyle card games, my win percentage is 65%, with the AI I would rank as an advanced player.)
Gin (the version of rummy where you keep all your cards in your hand and not meld them onto the table until the very end) is a fun one, too, but for some reason I get bored of it quite easily. I think it needs to be played for money to make it fun. The old neighbors would play penny a point, quarter a box, dollar a game. You probably should adjust for inflation.
The most skillful two hander and, in my opinion, the most interesting playing card game for two is piquet. It takes a little practice to learn but, once you get the hang of it, there’s great room for strategy and thinking. It requires a bit more concentration than something like cribbage to play well.
Two-handed versions of pinochle are fun, too, as well as its relative, bezique.
They’re all different types of card games, so its worth it to look and play through them all to see what holds your interest. Of the bunch, piquet is, in my opinion, clearly the one requiring the most skill and probably the greatest two-player playing card game of all time. I still end up playing cribbage much more often, though.
Oh, and one slightly obscure but quick trick-taking card game for two I’ve always enjoyed: Ecarte. If you like euchre, this might be the game for you.
Rummy. I just like it and it plays well with two people. Now we normally play Rummikub a tile based rummy game instead.