Sushi Go! is another good "getting people into not-awful board games" game.
Looking into buying a dungeon crawler now (cool map and miniatures preferred) and another game like 7 Wonders, perhaps Puerto Rico.
Can you recommend any games?
Dominion. The strategy arises from observing how the specific cards that are part of any given game interact with each other.
Agricola. There's a lot of "designed" complexity here too, but a good deal more arises, particularly when you look at planning the critical eight first actions, and the path to the first additional family member.
Tigris and Euphrates is an old classic that has very few tile types to place, but they result in complex outcomes. I can't say very much about it because I only played it once on a game show, but it's on my to-buy list.
Neuroshima Hex! is a bit nerdy looking, but it's simple without expansions. Retro apocalyptic setting with mutants and evil robots. A knife fight in a telephone booth, plays well up to 4 players. You fill up the hexagonal board with your troops (they mostly don't move) rotating them so that they will hit the most enemies. Then it either fills up completely or one of players plays Battle token, and everything goes off like a chain reaction. Units hit in melee or shoot in order of their initiative. High interaction, tight mechanics. Most people prefer it as a duel game though. You can play it online too.
(There is no "beginner's luck" in boardgames. There's "rule explainer's curse". The player doing the explaining is distracted, not just by explaining but also watching over anyone and often plays badly).
Also not surprised to hear that our group isn't the only ones playing a "Razz" (poker variant where you try for the weakest hand) variant of Sushi Go.
I found reversing points to make the game chaotic and more casual.
I'd counter the recommendation with something like