I found that a majority of the posts here are not very helpful (what's the second post have anything to do with the topic at all?). Warhammer 40k is not available on Android, from what I have seen (though I do agree it is an awesome RTS). The only good RTS I have found is that from Gameloft called Starfront: Collision, which is only available on their site, and only for a select few devices (it is an older title that hasn't been updated). It is very similar to Starcraft/Starcraft II.
There are some other "RTS" type games that have a different feel to them, and don't have very detailed graphics or story lines such as Auralux, GalaxIR or Galcon. I wish we had more RTS games though. Warfare Inc. would be awesome, as Neograndizer mentioned. It has a C&C/Starcraft feel to it (though outdated PalmOS graphics for 480*320 resolution). It would still be much better than what we currently have available.
If you want to try some Turn Based Strategy games I'd go with the one hamstar_ suggested, Great Little War Game (and the sequal Great Big War Game). Both have amazing graphics, cool little story lines and lots of replay.
"The only easy day was yesterday! Hooyah!"