For two players at that size I recommend Hanamikoji:
https://boardgamegeek.com/boardgame/158600/hanamikoji
It's a fast psychological game where you and your opponent draw these gifts that each go to a specific geisha and you want to win over a majority. The catch is that most of the ways to give gifts involve "fact or fiction" type choices where you group your gifts into piles and your opponent gets to take one before leaving you with the rest. I personally always enjoy the kinds of decisions you have to make; every game feels fresh.
Hive:
https://boardgamegeek.com/boardgame/2655/hive
It's a well studied chess like abstract strategy game that's been around for a long time. Basically you can either put bugs in play or move them around, trying to surround the enemy queen. You don't even need a board for it and it comes in a pocket edition. The moves are natural and interesting, the game plays pretty fast, there's a lot to love.
Radlands:
https://boardgamegeek.com/boardgame/329082/radlands
A dueling card game where both of you play off the same deck. You've each got random camps that represent your life and also have abilities you can activate, directing your strategy. You defend your camps with people and events that you draw from the shared deck, and you can even "junk" your cards for a minor effect if you don't have the resources to do everything you want. I have playmats for this which make the layout easy but without those you can easily fit this in a tote bag. Really well balanced with a great art style to boot.
I've got more but that's a good start I think.