Hanabi

The guys from Deep Mind said that it is one of the next games to solve.

Extremely simple rules and you can have a lot of fun, for 2 players or more. Basically, you have to draw some cards and place them in your hand facing the other players, in a way that others can see your cards but you can't. The goal is playing the cards in a certain order. You have to share information with the other players and remember what they know. Very original.

Codenames and Decrypto: Two teams compete on who can better transmit a message.

In Codenames, the two team leaders know which of 25 words belong to their team, which to the opposing team, which are neutral, and which one is the assassin. The goal is to give maximally efficient single-word hints to your team members, so they can identify as many of your side's words as possible without picking words of the opposing team (which gives them a point instead) or uncovering the assassin (which triggers an instant loss).

Decrypto takes place over a couple of rounds. Each round, one team member must use short hints to transmit a three-digit code of the form 124 or 342 to their fellow team members. Each team knows secret words associated with the digits 1-4, e.g. 1 = Metal, 2 = Hospital, 3 = Boat, 4 = Ant. So to transmit the code 124, one could give the three hints "Bronze", "Doctor", and "Tiny". The fellow team members then have to decode these hints, which in this case seems straightforward.

However, beginning in round 2, the opposing team gets a chance to intercept the coded message! They don't know your team's secret words (like "Metal"), but they know your past hints and what digits they were supposed to point at. So if your hints were too obvious (e.g. your past hints for 1 were "Bronze", "Hammer", and "Anvil"), they will over time get a good idea of what your secret words are, and thus become able to reliably intercept your messages. So your goal as a team member is to give hints that are sufficiently cryptic that your team members barely understand them, while leading the opposing team astray. That's a fun tightrope to walk!

Stone Age. Worker placement game like Agricola, but simpler, shorter, and more streamlined. 

Jaipur - best quick strategic 2p game I know of; hand management, risk assessment, heuristic position evaluation.

Codenames - very good mix of cooperation, competition, other-mind-modeling, cleverness, not-being-too-clever, different levels of engagement, even trolling. Two teams of 2+ people apiece. Can be problematic for ESL. Word association, risk management.

Werewords - best quick party game that's not boring that I know of. A cross between Werewolf and 20 questions. Bluffing, language, social deduction.

Goa - most interesting economics of any game I've ever played, especially when playing with 2 players. The whole game is good but the auction mechanics involve paying your opponents and growing or shrinking the overall cash in the game so it becomes very very tricky to figure out what value to put on your own cash. Auction, hand management, kindasorta engine building.

Personal favorites for different reasons are Race for the Galaxy, Terraforming Mars, and Mage Knight, but I have no reason to believe they're some kind of general attractor. If you're just browsing, or love one and haven't tried the others, browse them too.

Spirit Island. It's inverse Settlers of Catan - you (cooperatively) play as the island and you use your powers to evict the settlers' cities. Requires an enjoyment of puzzles, and being willing to muddle through the first game to learn how it works.

The Treacherous Turn

I'd be remised on an AI forum not to mention the AGI TTRPG (a small team and) I have been developing for the last 6 months, with Daniel Kokotajlo at AISC.

In the game, the players collectively act & strategize as a misaligned AI in conflict with humans in a realistic near-future setting. The goal of which is to spread awareness of AGI safety issues, and make inferences on how an AGI might act based on the strategies players pursue.

It is as yet unpublished, you can find status updates here: https://thetreacherousturn.ai/ 
I could possibly get you a copy of the rule set if you're interested.

Sort by susd recommended + desired category on this website:

https://www.shutupandsitdown.com/games-page/

My preference is for games that can be played with people who are new to them (i.e. don't have hordes of fiddly tokens or large numbers of separate rules/mechanics), and that don't demand you do the thing under time pressure (as with 'party' games like Articulate/Pictionary)

Some favourites have been Cockroach Poker (simple card game of bluffs and lies and reading people), Camel Up (betting game around a simulated camel race, with enough chaos to how they move to make explicitly calculating your best move a fool's errand), and Dixit (love the art and free-association of it)

Honorable mentions to Discworld: Ankh Morpork, Photosynthesis, Smash Up, and Small World. Although at least some of those veer into the realm of fiddly tokens.

The Crew. One of the few good cooperative games. You can’t speak during a round and have only a few ways to communicate to solve the puzzle together. The campaign adds complexity over time to make it stay interesting as the group learns the tricks of the game.

Mindbug. Made in part by the creator of Magic the Gathering, but made much more accessible to play with new people. Still, it is really deep. The core idea of mind bug is that you can take control of the card the other player wants to play (with your mind bug), this creates a lot of mind games as you’re trying to trick the other person to steal a card at the wrong moment (you only have 2 mind bugs per game).

Wavelength. Can play with almost any group and possible to play at high player counts. No need to play in teams, so no uncomfortable competition when trying to have a good time even with new people. Creates interesting conversations and is really fun and replayable! Good for getting to know one another too.

Brass: Birmingham. One of the best Euro games. Industrial revolution theme, understand the market to make your industry win. Other people can use the industries you build so it makes for very interesting strategies.

The Quest for El Dorado. One of the best deck-building games. The hexagon boards can be placed in a lot of combinations to create variation between games, and you can remove some cards from the store to make the strategy change a lot between games. I love it.

Gloomhaven. Another great cooperative game with a good system that creates many fun puzzles to solve. You unlock new ways to play, aka. new characters with new cards and new rules to learn and master in combination with your friends’ characters. Many cooperative games suffer from the problem that one person can decide what others should do. But here you’re not supposed to show your cards to each other at first, so you get both autonomy and cooperation which is nice so everyone feels they have an important role.

Oceans. Strategy-game, compose reliable species that thrive in the ecosystem. Fairly simple rules but hard to master. Lots of unique cards and randomized conditions make it fun and replayable.

Skull. Simple but really fun bluffing game. Easy to bring to a bar or restaurant and play a quick round or two.

Bring Your Own Book is a light social game you can fit in your wallet (just take a subset of the cards) and play using whatever text you happen to find around you in the real world. There's a free version you can print and play on that site, or you can buy a fancier boxed version. Anytime you are in a group of people and there's some kind of text you can grab around you - even restaurant menus in a pinch - this game is a delight.

Glory To Rome is my clear favorite group competitive mechanically-heavy card game. I've played it more than a 100 times. It's fun as a beginner and fun with an expert group. The meta never seemed to settle - there was never a consensus on the best strategies even with extensive playing. Something about the drafting and card interaction dynamics of the game mean it's self-balancing. The thing I am most surprised by is that I still have sessions where the game ends up in a state or a dynamic I've never seen before. The rules interact in chunky and explosive ways that keep things interesting. 

The game is out of print, caught in some kind of legal limbo, so you'll have to hit up used markets or print and play your own unofficially. Worth trying to get it though. I prefer the original ruleset, but there's tons of fun to be had mixing in some portion of the expansion cards from the Black Box. Even a few cards can swing the game in pretty wild ways. I've tried the designer's other games which on the surface have similar mechanics. They aren't bad but none captured the magic of Glory to Rome. Please, somebody, get some lawyers and get this game back in print!

A couple things that would be good to know:

1. What level of complexity are you aiming for?  I play a lot of board games, but my personal favorites are ones I wouldn't necessarily recommend to someone who wasn't similarly obsessed, and I also try to keep around a lot of easier games to lure people in make the hobby more accessible to new entrants.
2. How many players do you have?  Some very good games are 2-player and cannot take more - some require 4+ players and can't be run with only 2.
3. Do you have a preference between euro-games/non-euro-games?  If you don't know what this means, put 'no'.

A few things I might recommend on the lower-complexity end:

Fairy Tale 

Summoner Wars

7 Wonders

Kingsburg

And on the higher-effort end:

Mage Knight

Gloomhaven

Twilight Struggle

War of the Ring

Eclipse

In general, I'd also recommend boardgamegeek's ratings (you can find a list of games here, and can sort by rating).  I don't 100% agree with their ratings (Pandemic is not my cup of tea, and Star Wars Rebellion being as high as it is is a travesty), but they're generally a very good starting point for 'is this game good'.

Innovation: The history of the world in a simple, elegant, ever-novel package.

Tigris & Euphrates: The rise and fall of empires in the cradle of civilization. Yet elegant and strategically deep instead of the usual dudes-on-a-map stuff.

High Frontier 4 All: Like Kerbal Space Program, but a board game. Has a realistic map of the solar system so beautiful and interesting you want to spend hours just staring at it.

Eclipse: If you like space opera, if you like dudes-on-a-map games, if you like 4X computer games like the Civ series, then this is the board game for you.

Santorini: Like chess, but with simpler rules + every game is different thanks to a big set of special god powers. Also 3D because you are building a town and hopping from rooftop to rooftop.

Android: Netrunner: Like Magic the Gathering but asymmetric and cyberpunk. One player plays as a big corporation trying to advance hidden agendas; the other plays as a runner trying to hack in and steal their secrets.

Zendo, which I've heard called "science: the game". One person acts as the game master, coming up with a secret rule that matches certain arrangements of the game pieces. (Typically stackable pyramids, but lego works, and I've played through discord using emoji.) E.g. "no pyramid is pointing at another pyramid" or "there are more red pyramids than pyramids on their side". Other players work to figure it out - in theory that's competitive, but IME it's pretty common for them to end up cooperating when the rule is tricky.

As a player I enjoy getting to look at a bunch of evidence, form hypotheses, run experiments and generally try to figure out wtf is going on. As the game master I enjoy seeing what completely unexpected directions my players thoughts run in, coming up with rules of a good difficulty level (illusion of transparency!), and using counterexamples to either give them useful hints or not according to mood.

Mystic Vale (review)

Deck-building game similar to Dominion except you use transparent layers in sleeves to modify/assemble individual cards in your deck.

Anno 1800. Supply chain management: the game. Competitive, but unlike typical worker placement games your moves primarily help other players instead of hurting them. [If I make a building that produces brass, you can now trade for my brass.]

Great Western Trail. Everything good about an eurogame, player interaction in a sweet spot (neither "multiplayer solitaire" nor a "take that!" free for all), and little downtime.

Or Grand Austria Hotel if you want something more puzzle-y.

I'm a big fan of social deduction games like Mafia and Werewolf, but my favorite is Secret Hitler.

In the game, each round sees a government (President and Chancellor) elected, following which a policy is passed (either liberal or facist).

Players are either liberals or facists, and the latter know who each other are while the former do not. A single facist is also Hitler.

The facists win if they can pass five facist policies or, alternatively, pass three facist policies and get Hitler elected Chancellor.

The liberals win if they can get five liberal policies passed.

Very fun, and unlike Werewolf, players aren't killed off each round (so you don't wind up with someone basically not playing the whole time).

Wingspan is probably my favourite game currently. It's an engine building game were you collect birds. Gorgeous board and cards, very interesting gameplay if you like to plan your moves in advance. One particularly interesting part is that there are four rounds which are increasingly short, so as the game progress you get more powerful turns but less turns. Not a whole lot of player interaction though. There is a solo variant too.

Photosynthesis is a great game where you want to grow trees. Bigger tree get more light but they shade other trees, so you want to plan where to put your trees as the sun circle the board. Really complex game with rather simple rules. https://boardgamegeek.com/boardgame/218603/photosynthesis

Ultimate werewolf one night is the surprisingly good real game version of the famous party game. It's a hidden roles game were villagers have to find the werewolves. It happens in only one round : one night were everybody act and then one day for debate and vote. The good parts : 0) no need for a game master 1) almost everyone can get information during the night (I strongly recommend putting only special roles and no base villagers). 2) nobody can be sure their card didn't get switched during the night. In particular you don't know if you are in the same team as when you started the game (you don't look at your card in the morning). 3) you can really reason your way out of all of the lies, it's not posturing then random guessing.