Battle for Mars has been out for a while, and was my first "favorite" game for Android. It's a turn-based strategy game and it's quite fun. I put a couple screenshots below and a link to their website so you can find out more.
Why am I shilling for this developer? Because they've added a multiplayer game and there aren't enough people playing. The game was great single-player but now that it has the multiplayer function, it's even better. What I like about it is that you don't have to commit to a whole game in one sitting to play multiplayer - games can go on for days as all players take their turn when they have time.
Seriously. Check it out. Play against me.
Link to their website.