Just get Civ IV or V.

Age of Wonders.  Its a pc game, but even if your pc is really old you should be able to play the first one without problems at all.

imperium galactica 2 its more of a realtime 4x think of it as a precurser to sins of a solar empire

civ 4 and all the mods for it. (can t run civ 5 on my rig or id have it)

Europa Universalis: Rome   game rocks out loud

Empire: Total War also rocks

You could try Magic: The Gathering on XBLA.

Agricola

A game being complicated doesn't mean it has depth.

For instance, Civ 5 has a pretty simple control scheme and could easily be put to controllers.

I think a great example of complexity and depth is actually Dungeons and Dragons.  I don't know anything about the first edition, but I've heard horror story after horror about how difficult second edition was (or AD&D I guess?).  I've had people explain it to me and it just sound painful.

And then 3rd and 3.5 came along in 2000 with the d20 system that revolutionized the system and simplified it in a strange way.  The game was still complex but they made it far less confusing and kept all the depth.  It was a pretty big transition.

And then 4th edition came out two years ago which streamlined the game like crazy but added a crap load of depth.  In 3rd edition if you played a caster you would have a grand old time, but if you played something like a fighter, you just basic attack, basic attach, basic attack, basic attack and keep all the complexity of the game.  With 4th edition, they made even a level 1 fighter a lot of, made the game incredibly easy, and added depth to every class.  They even standardized role playing with skill challenges.

I know I'm on an extreme tangent here, but a turn based strategy game isn't hard on consoles, it just isn't popular so nobody has felt like making it consoles yet (or nobody with money).  With Civ V, that would be an incredibly easy port from mouse keyboard to controller.  The mouse would likely be better, but it still wouldn't be bad by any means.  And then you have things like the Heroes of Might and Magic series that would be just as good with a controller.

So!  In short, complexity doesn't equal depth.  In the case of D&D, the least complex of all the editions actually has the most depth to it.

Ugh, that game is awful.

You can't actually build your own deck, you can just add cards to an already premade deck.  Let me take my collection of cards and just make a deck.  I know they want to make it beginner friendly, but let me decide my own damn land ratio and get rid of the terrible cards it starts me with.

Also, that 2.5 second timer.  I hate that timer.  It's one of the worst things ever put in any game.  I haven't played that game in a while so I don't know if they removed, but that timer happened after every effect.

I really wish they would have made the interface more like MTGO, that would have been great.  About the only good things about the XBLA game is the puzzle section but that's not really something for beginners.

The Heroes of Might and Magic games (especially the 3rd one). Most of them are really old, so you should be able to play them on an old PC. Also the turn based tactical RPGs for Nintendo's handhelds are cool too.

Advanced Wars for DS was7 is great.

And on PC? JaggedAlliance2, of course:) Best game of all time.

And you are so right about less CoShitty and more strategy-games.

Since you don't game on the PC:

Advance Wars for GBA and DS

Fire Emblem for GBA, DS, GC and Wii

FFT for PS1, GBA, DS and PSP

Tactics Ogre for GBA and Wii Virtual Console

Luminous Arc for DS

I think that should be enough.