I'd look into something tactile, with simple rules but strategic depth:

Personally I'd recommend Hive or a similar (and simpler) tile movement game, High Tide.

https://boardgamegeek.com/boardgame/2655/hive

https://boardgamegeek.com/boardgame/430875/high-tide

Both have nice chunk tiles, no board requirement, few pieces, and can easily travel. And they can both be easily explained.