I enjoy playing Axis and Allies as a casual game, but as a strategy game it has about as much depth as Risk, a game whose depth of strategy is aptly described by its name. A&A suffers from the lack of a fog of war and the resultant strategic possibilities and pitfalls, as well as an oversimplified probability mechanic. The pre-arranged and unchangable alliances don't help matters any. And then there's setting up all those damn pieces...
A simple game I
would recommend is "
Diplomacy", which is set in pre-WW1 Europe. Nothing is left to chance in this game, but rather to your ability to think creatively and read other players. All moves are planned secretly on paper (which you may or may not choose to reveal to others) and made simultaneously. The actual game mechanics are a bit like GO, which is to say that they are focused upon guile and maneuver, but the real game takes place between the players, not on the board. No single power can stand alone at the outset, so the emphasis is placed upon, unsurprisingly, diplomacy.