Five Tribes is a multiplayer, Mancala-like worker-placement game (designed by Bruno Cathala) that we have played on more than a few occasions. It was the 2014 Golden Geek Best Strategy Board Game winner and has received high praise from a number of boardgamers.
Each turn you select a square and pickup the meeples on it, placing them one at a time on adjacent squares (making a path orthogonally around the board). When you place the last meeple in a square, you get to take an action based on the color of that last meeple (and others matching that color in that square).
There are two aspects that I like about the game. First, the bidding mechanic allows you to spend an amount of victory points to increase your chances of going first (in case you see a great combination or move to start the next turn). Second, I enjoy the brain-burning aspect of the game, in terms of the vast number of options and plays you can make each turn.
In general, it seems that there are different paths to victory and it is enjoyable to make a high-scoring play that others may have overlooked. I recommend trying it out if you are looking for a mid-length four player game.