One of my favorite games is Carolus Magnus. I have described it as Chess on steroids because you need to plan a couple of moves ahead, but watch out! Your plans can be thwarted with the single move of another player.
You are vying for control of Charlamaine's empire. At the beginning of the game, his empire consists of 15 territories. Control is determined by cubes of five different colors and a tower of your color (black, white, or gray). You will always have control of your own towers, but the person who controls a particular cube color can change, which can cause territories you thought you controlled to swing to another player.
At the start of the game, the territories are layed out in a circle and seeded with a single cube. An emperor token is placed on one of the territories. You then fill your personal cube supply and a starting player is chosen.
Game play goes like this: You have disks numbered 1 to 5. In turn order, you put down one of your disks. You can't play a number that another player has just placed, unless you don't have any other choice. The numbers on the disk determine the play order for the round, lowest to highest. Sometimes it is advantageous to go first, but you can't replay a number until you've used all five, so you will end up going last in some rounds.
Once it is your turn to play, you examine the cubes you have in your supply and can place some cubes on territories to try to win them over. Optionally, you can place cubes in your court to try to win control of a specific color. The player with the most court cubes of that color takes control of it. The number of cubes you can play varies with the number of players, so consult the rule book.
After placing your cubes, you move the emperor token clockwise around the territories. You can move it from one territory up to the number on the disk you played in that round. When the emperor stops, you evaluate the territory where it stopped to determine who owns it. The person who controls the most cubes plus the tower color, if a tower currently sits on the territory, takes control of the territory. If ownership of the territory changes, the new owner places a tower of their color on the territory. This may cause the tower of the previous owner to be removed. If you now have adjacent territories owned by the same player, they are pushed together to form a larger, more powerful territory.
You then role the special dice that show which colored cubes you take from the supply to restock your personal supply. Play then moves to the next player.
The winner is the first player to place all their towers.
In many games I've played, I found the person who comes into power first, often loses when control suddenly flips to another player. This adds a great element because you don't know when the tipping point will occur, or even if it will.
I have found Carolus Magnus plays really well with 2, 3, or 4 players, but is especially good with 3 players. Rules are slightly different for 4 players, but does not take away from the game. Play time is rated at 60 minutes. Some games have taken the full 60, while a few have finished in as little as 15-20.