My goal is to have a game that I can carry around with me, walk up to people I meet in public, and ask them to play.

Is it just about portability or do you also need a small playing area?

I want the game to be strategic with minimal luck but simple enough that a first time player could reasonably win against someone experienced.

Those goals are at odds. If there's minimal luck, there's little room for the new player to win in a strategic game.

That being said:

• Azul can be quite portable (if you dump the box), but needs some playing space. It's vicious with two players, the more experienced player will usually win, but the rules are simple enough for a first time player to at least understand what happens.
• Onitama is chess-like, with simple rules and some randomization that prevents the need to memorize start sequences and the like.
• Arboretum is a tight battle with two players. You constantly need to worry which cards to play in order to gain points, which cards to keep in order to even be eligible for scoring and which useless cards not to drop, because they might be useful for your opponent.
• Kahuna is a bit older, with simple rules but some strategy.
• The Fox in the Forest is a two player trick taking game I found rather enjoyable (and I don't even like trick taking games).