How big a screen? I've played some good RTS games on my Nexus 7, but I wouldn't want to play them on something with a small screen.
Eufloria is fun as a super-simple RTS. Very slow pace, though, lots of waiting until you've built up enough seedlings for a push. Stylistically it's neat looking - with the constantly-flying stuff and the light space sky it visually reminds me a bit of homeworld (although the gameplay isn't like homeworld at all).
Swords and Soldiers I had a lot of fun with. It's a simple RTS game... not much actual "command" - you choose what units to build and cast spells to enchant them or harm foes, but you can't actually control the units. They just march forwards and attack the first enemy they see. The gameplay is actually just a 1D line where you push the front back and forth. Still, it works and it's solidly good fun.
Both are noteworthy in that most phone RTS games are simply tower-defense, whereas these games put you on even footing with the enemy who uses the same kind of army as you. Eufloria is single-player, and S&S includes a split-screen mode if your'e crazy and have a huge tablet.
I'm actually surprised we don't have Civilizations Revolutions on Android - my freaking WinPhone has it, as does my DS.
edit: 1 day left on the Humble Bundle android sale, including Carcasonne (classic Euro tile-laying boardgame). Carcasonne is fun but I haven't played the Android port yet... in general the Days of Wonder phone games are hit and miss.
https://www.humblebundle.com/
