I'll admit, I don't keep up too much on Gameloft's Android offerings, but the developer has received a reputation for releasing some of the higher quality Android games available (just not on the Market).
Their latest offering, whose release date is unknown, is March Of Heroes. What makes March Of Heroes different is that the game has been built on the Unreal Engine, which is a much more configurable and modern engine, and is probably the most advanced game engine on any mobile platform.
We don't have any information on a release date or pricing, but Gameloft generally churns out titles pretty quick, so you probably won't be waiting too long. Here's a video: