I'd recommend
Philip Muwanga's Hexy Trench. The unfortunate thing is that the demo time limit sucks for this game, because it takes a little while to play through the tutorial.
I'll start off by saying I think the game is well worth the $2.50. There's definitely more than enough meat there and the game is good enough that you'll be able to get at least a few hours of fun out of it if it's up your alley. Still, I feel like it needs a bit of explanation, so I'll go ahead... To do a Bettenhausen, Hexy Trench is a (very) simple puzzle game meets a tower defense game meets a real-time strategy game. (BTW, I have no idea who Philip Muwanga is, but if he's planning more XNA games, it's not a bad idea to make your name part of the game title... it'll make it easy to find the next game in the series)
Anyhow, the puzzle aspect is trench-building - you get random pieces to build a trench out from your base. The trenches are the only place you can build structures, and they also link you to supply-producing outposts.
The structures you can build are spawn points for grunts, who are like tower-defense enemies who march blindly in a straight line, damaging whatever enemy structures are in their place -- bases, trenches, buildings, etc.). There are also machine guns (anti-grunt gun batteries) and artillery (slow-to-recharge offensive weapons you control to soften up emplacements such as those pesky machine guns)
It's all pretty simple "destroy the other guy's base" gameplay, but it works well. There are weapon drops -- some of which may be a little overpowered -- but the game is generally pretty intense (and there's an option to create custom rules. It would be nice to see the ability to vary the AI a little (you can only choose one AI level for all your opponents), and I don't think you'll ever find someone random on Live, but the game is still very entertaining.... it also comes with a low-rent twin-stick shooter (not at all worth the price of admission, BTW). For a hardcore strategy fan, it might not fit the bill, but for my shallow tastes I'll be going back.
I think generally, the game is a bit busier than this screenshot, but it was the first one I found
Everyone else has mentioned Miner, which is good. Someone referenced the "produce a game ad" submission so I'll repost it here