A friend and I sometimes play a game called Scotland Yard that might fit your bill. In this game up to four players take the role of the London police, and one person takes the role of a Mr. X, a criminal. The players navigate the city streets and subways of the city trying to capture or elude one another.
The police have superior numbers (there are always four, even if only one player controls them) but Mr. X has the advantage of being invisible for most of the game. The police must try to corral him using clues from the modes of transportation he takes, while Mr. X must use misdirection to throw the police onto the wrong trail.
This game can be game can get pretty intense and requires a lot of thought. It definitely works as a two person game – possibly even better as one because the police will have a more unified strategy without the need to discuss it with others.
A word of warning, though: the roles are very asymmetrical and sometimes people who are new to it perceive this as being unfair. E.g.: “The police have all the advantages, it’s impossible to win as Mr. X”, and so forth. Having played this game a decent amount I think both sides present fairly unique strategic challenges, though Mr. X probably has a higher learning curve.