There are plenty of simple games out there. I'd recommend a trip to a local game store. My friends Chris and Will run It's Your More on Telegraph Ave 51st street in Oakland. I can promise they can find you a board game with a degree of complexity you would like, since available run gamut from extreme simplicity to extreme complexity.

That said, I think complaints about complexity sometimes miss the way elaborate steps can be a sort of calming ritual rather than a part of the game as intellectual strategy and one's preferences there are personal. I personally love the game of Go, a game that probably achieves maximal complexity among face-to-face strategy game but I have seek out other players of this since none of my friends are interested.