Correct me if I'm wrong, but Valkyria has no trophies, only an internal medal system, not linked at all with PSN Trophies.

I always wandered why Ubisoft doesn't do a proper HoMM game for consoles. It's hard to navigate the options, but you do have the time to do it no?

And now that we have pointer devices on consoles, they should really do a full port of Heroes 3. Endless online Heroes 3 1v1, Huge, no underground, no water, random (:P), impossible, Strong....no diplomacy...what else?.. a, no sir. Mulik.

For consoles definitely Valkyria Chronicles.

IMO it's as much RPG as Advance Wars. Pretty much no RPG at all or at least not much more than any other game from a different genre. Simply turn based strategy.

For PC (even though you said you don't play on them) Civilization II and Heroes of Might and Magic III. Classic.

Anno 1602 a TBS ? More like an RTS or economy simulation.
Did you try Anno 1404 Dawn of Discovery yet ? I think that's the very best of the series.

Advance Wars.

With my first post, I'd like to say : X-COM UFO DEFENSE!!

Master of orion 2. You need to play that game. Honestly. :D

Suggestions for a 360 owner. Its sad that no one has kept it on-topic for 360 games :-

1. Culdcept Saga. Its like Magic: The Gathering mixed with Monopoly. Unlike the XBLA game, you can build your deck. Its a wicked, but difficult and rewarding game. You take turns with your opponents rolling dice, and placing your cards to claim land. You build them up like monopoly, but if an opponent lands on your square, your cards battle it out. If they lose, their card dies, and they are taxed ala monopoly. Great game.

2. Tropico 3. Its not turn-based, but its realtime strategy. It is, hands down, the best strategy game on the 360. Its a cross between Sim City, Sim Farm, and Command & Conquer. Absolutely fantastic, and I cannot praise it enough. Brand new, it was $40. I'd imagine its cheaper now. Although its not TBS, you can pause and slow down the gameplay, which allows it to be at least at-your-own-pace like a TBS.

3. Civilization: Revolution is pretty decent. Its not great when compared to mainline Civ games, but its still pretty good.

Also, Viva Pinata is a good game, albiet non-TBS.

almost forgot PTO II for the SNES ... its a gold standard ... if console  patching had existed back then it would be perfect

Advance Wars for the DS and the real PC Civilizations. 4 and 5 do different things, so look into both of them.