Well, I have a few suggestions, but some of them aren't specific to Android, I don't know if that matters or not, but here goes:
Eufloria: An RTS-lite so to speak. There's no real base management in the game and the strategic depth is nowhere near a fully fledged RTS. However, it's a great game, very laidback and not really on the hard side in terms of difficulty. There is one type of unit, but the stats of the units vary depending on which asteroid they spawn from. Asteroids can be planted with trees that come in different shapes, like offense(which spawns seedlings, the attack units) and defense(which spawns defense mines, when you get invaded). I've had a lot of fun with it, both on my phone and on my PC, with the latter being where I've spent the most amount of times, due to the modding community.
Next up is
Superbrothers: Sword and Sworcery EP(not a typo). It's an adventure game with a very cute art style. It's done entirely in pixel art, yet I never felt you couldn't see what was going on, on the screen. The soundtrack is also really excellent and fits the mood of the game perfectly.
Machinarium. Another adventure game with a sweet story about a robot boy getting lost, trying to find his way back into the city. Some of the puzzles might be a bit obscure, but there's a hint system built into the game, so there's no reason to ever quit the game, because you're stuck. It's a great solution, since it can keep some of the old-school style puzzles, but still help more inexperienced players get further in the game.
Splice. I'm not really sure to how to describe this game, honestly. The goal of the game is to splice(hence the name) cells to specific forms given by the game. I guess it's a puzzler in that regard, but it's not really like something I've played before. It's quite rewarding when you actually solve some of the later levels, because they can be pretty hard.
ScummVM. The engine for running the classic point-and-click adventures, like Monkey Island and the like, that you can get on places like
GoG if you don't have them on CD or something similar. If you've never gotten around to playing those, this is the perfect opportunity for that.
NetHack. NetHack is the legendary roguelike that have been around for many, many years and is available for play on Android, which is great. It's not for everyone, but I'm still going to throw it out there, in case you want to check it out.
FreeCiv. Civ on the go! It's basically Civ2 for the Android. It's a little hard to control on my phone, since the interface is quite small with such a small screen, but I can imagine it working a lot better on a tablet if you want to check it out. If you don't know what Civ is(which you probably do), it's
the empire building game, starting with a puny settler but eventually building your a globe spanning empire so that you can crush your enemies to death!
Anyway, I hope you can use some of my suggestions. I know it's very adventure-centric, but the platform really lends itself well to turn-based and/or slower based games, which all of the above really are.
EDIT:
Quoting so you'll get a notice:
bluegate said:
EDIT 2:
You're in luck, there's a new
Humble Bundle for Android on sale right now.
r Any good Android games out there ? 
