I'll second Band of Bugs on the Xbox 360, but that's going to be about it on that platform. You might also want to try Outpost Kaloki X, also on Live Arcade, as it's also a (quirky, sort of-)strategy game.
Your big win for strategy games on a console would be on the GBA, where you have a lot of options. First and foremost, Final Fantasy Tactics Advance, a sequel to Final Fantasy Tactics. There's another sequel currently in development for the GBA. Tactics Ogre: The Knight of Lodis is also very similar, and better IMO.
There is also Shining Force: Resurrection of the Dark Dragon, Fire Emblem and Fire Emblem: The Sacred Stones, and both games in the Advance Wars series, all of which are excellent.
Another option is the PS2, which has a fairly decent library, but turn-based strategy games have kind of fallen out of favor on non-portables. You can find a whole slew of games developed and/or published by Nippon Ichi (Disgaea, etc) that might fit the bill, but they tend to be on the odd side, and hyper-anime-kawaii, so you'll either love them or hate them.
Recently, the PSP seems to be picking up some as well. Jean D'Arc and Final Fantasy Tactics: The War of the Lions were both recently released, as well as tactics games based on both Dungeons & Dragons and Lord of the Rings. I haven't tried the latter, yet, but the first two are both quite good.