Oxenfree - Fantastic voice acting, good mystery elements and a compellingly creepy story that makes it fun to experience with others. Not a ton of traditional puzzles to solve but plenty of choices to make that determine how certain things play out. However, the dialogue choices can go by pretty quickly so if you two like to debate and take your time choosing how to respond you'd have to be willing to just choose what feels right without dwelling.
Tacoma - Figure out what went wrong on a space station.
Disco Elysium - This would be a fantastic one to play together. It's all choice based and sometimes failing is better than succeeding, giving you multiple ways to accomplish what you need to do in drastically different ways. There's no real rush to anything so you can take your time making decisions and wander around a ton. That said, it is very elaborately written with lots of narration and voice acting, perfect if you like stylized writing and dialogue, not the best choice if you prefer flashy cut scenes and heavy action sequences with your story.