In my group of friends we have more than 50 games, most of them involving complex strategy (as we do like that). Here is a list of my personal top 10:

1) Shogun. Archetypical Risk-like game of moving soldiers and conquering provinces, but with a unique twist that makes it outstanding in my view: instead of dice, it uses a cube tower to generate randomness. The outcome of fights is based in the number of cubes from each player that come out of the tower. If you get bad luck in a battle (because your cubes stay inside) then the tower will be loaded in your favor for the next battles (those hidden cubes can come out at any moment). I love this because, although I think some randomness is good in strategic battle games to spice things up and so that the game doesn't turn a chess-like prediction game, I don't like the winner being dependent on luck. The tower introduces randomness, but guarantees that no one will be too lucky or unlucky, which is great. Combine with a setting in feudal Japan, complete with rice farming and starving populace revolving against you, and you get an amazing game.

2) Imperial 2030. Another typical Risk-like game of moving soldiers and taking countries... except that it's not. You don't control the empires themselves, instead you are a banker that buys each empire's bonds. At a given point in the game, the banker that holds more bonds for a particular empire is the one controlling its politics. So maybe right now I control China, but I know that you have a lot of cash and are looking at Chinese bonds with greedy eyes, so I send the Chinese army on an unnecessarily painful military campaign to wither down its power in case you are going to control it in the next turn. This makes for awesome mechanics in a really strategic game. By the way, it doesn't have any random elements at all, so it's a good game if you are against that.

3) Galaxy Trucker. This game is great due to its sheer concept... first you use pieces from a scrapyard (competing for the pieces with the other players) to build a spaceship with its cannons, shields, cargo holds, etc. and then all of you have to fly them in a journey littered with space pirates, meteorites than can tear off pieces of your ship, merchant planets, smugglers and more. The feeling when one of your rival ships is tore in two by a meteorite is unbeatable.

4) Star Wars: Imperial Assault. When a friend of mine got this game, I thought "they have the Star Wars franchise so it will probably be a crappy game - they will sell anyway". But no. It's actually a very good tactics game with lots of choices, characters with very different styles, special abilities, and a set of rules that (albeit unspecified at times) go very well together.

5) Robo Rally. A classic from Richard Garfield, the guy that brought you MtG. OK, maybe this doesn't fit that much into "complex strategy", but it's also a game that hackers should like because it's about programming after all! You have to program your robot with randomly-dealt cards to try and survive pits, traps and the other robots' lasers. A huge strong point of this game is that the maps and missions are hugely customizable, supporting different sets of rules like races, capture the flag, deathmatch, and others that you can come up with. It supports up to 8 players, you can build different maps putting together map boards, and there are editors online to print your own map boards, so it's the ultimate customizable game. I think it's out of print but a new edition has been announced, although it only supports 6 players sadly.

6) Carcassone. One of the best known modern board games, together with Catan. But while Catan is IMHO too shallow and too random, featuring few meaningful decisions, in Carcassone every tile you place is a meaningful decision. The experience is very different in 2-player games (much more offensive) than in games with more players. Some expansions (the builder, the granary and pig, the mayor, the resources, etc.) really enhance the game although others are prescindible.

7) Discworld Ankh Morpork. A deception game: you have to work towards your goal and the other characters don't know what it is. You don't have to know Discworld to like it (one of my friends hasn't read any of the books and loves it). Drawback: unbalanced, it's easier to win with some characters than others. If you care much about that, it's probably not your game.

8) Goblins Inc. Similar mechanic to Galaxy Trucker (probably inspired on it), but with goblins that build robots of doom instead of spaceships, and with direct combat. Contrary to Galaxy Trucker, it's team-based (2v2) but it also gives you the possibility of being a traitor to your partner. Less flexible than Galaxy Trucker (this one only really works with 4 players) but loads of fun!

9) Power Grid. A classic game where you have to build a power network. Lots of strategy and decisions, although the beginning depends too much on player location and the endgame turns a bit too much into an arithmetic-fest counting to the last nickel IMO.

10) Escape from the Aliens in Outer Space. A quite original board game in that it doesn't have a board, the board is in each players' head. Some players are humans and others are aliens, but they can't see where each other is, except with certain clues (people making noise) and items. The humans must escape the aliens. It's a lot of fun and it involves both abstract thought and psychology/bluffing/etc. The drawback is that some maps and situations can be unbalanced, especially if you play with the stock rules (a door to exit the ship can randomly work or not) a player can lose very unfairly. It should be pretty easy to customize the rules though.

Also go is awesome, but I don't think it's the kind of game you were looking for advice about (and it's difficult to compare to the others as it's on an entirely different category).