I want an RTS with some depth and some sandbox elements on Android. Playing on a smaller screen would be pretty cramped, but I bet it would be fine on a tablet.
I remember when ZodTTD released OpenTTD, a Railroad Tycoon game, for iPhone. This was before the iPad was released, and this app was only on Cydia. It was very hard to play on the 3.5" screen, but had a lot of the in-depth elements that would make gamely rewarding.
Haven't seen a game like that since that isn't watered down to death for mobile.