Frankly, I just look at AppShopper and download whatever looks good and is marked down (to free usually). Here are some (not as common) games that I've enjoyed a bit on iPhone and iPad:
Splode (Universal) - A physics game where you tap the screen to create an explosion knocking nearby spores toward other spores in hope that you create a chain reaction. The game typically requires that you get a set amount before you can continue.
Infinity Field HD (iPad) - Pretty much the best Geometry Wars clone that I've played on the iPad. Unfortunately, it still falls to the same issue as GW in that the easiest way to win is simply move slightly away from enemies while shooting in a circle the whole time.
Collision Effect (Universal) - A sort-of-physics game where you get a blank space and these gem-like "Zybbles" will appear on your screen from any point on the side. They will move across the screen in a set direction. When you touch them, that zybble will stop all zybbles of that color will move (quickly) toward the touched one. If two zybbles of different colors collide, you lose. You get combos (double, triple, quad, super) if you cause them to combine within rapid succession. A quick tip for this game.. do not attempt to create combos near the end of a stage. The game has a score multiplier; however, your multiplier will fade if you don't score any points within about 5 seconds or so. The end of a stage will cause your multiplier to fade because of the lack of zybbles, so I typically save the last two to keep my multiplier alive.
Kenken / Kenken Pro (iPhone) - Sudoku with math. It's actually rather fun if you like Sudoku. The original supports up to 6x6 and Pro supports up to 9x9. I prefer the original's progression with its pre-defined ~255 boards per difficulty as you can see how much you've accomplished. The Pro version supports drawing numbers.
Trainyard (iPhone) - A game where you're given a grid that contains train starting points and end points and you must draw the tracks between them. The hard part is... you have certain colors that trains spawn as and each end point is color coded. Trains can collide to combine colors (yellow + blue = green, etc). There are also two types of modifiers: scissors, paint brush. Scissors will split your one train into two, and will also split a non-primary color into the original primary colors (green will be split into yellow + blue). The paint brush will pain your train in the color that is shown.
If you want to see some examples of what the solutions look like, check out the website:
http://www.trainyard.ca/ . I will tell you... they get pretty damn crazy.
Cut the Rope (iPhone or iPad) - Probably my favorite physics-based game on the iPad. You essentially get a piece of candy from the starting place to Omnom's (a cute little frog-like creature) mouth. This can involve swinging it on ropes, cutting said ropes or using many other theme-inspired devices (gravity switching, magic hats, etc).
Hanging with Friends is pretty good. There is a paid and free version on iOS, not sure about Android.
it's from the creators of words with friends, but it's hangman.
I'm really not a fan of that game. My largest gripe is the fact that you rarely win by skill but by luck. I can almost always win by using 4 letter words. You get 8 strikes, but they're nearly impossible to get unless you are lucky enough to get a consonant.
For example, one time a person played "JOKE" and I had "_O_E" with 5 strikes left. I tried to play valid letters that I knew were in multiple words, but it doesn't help when you're essentially left guessing. Even if I guessed 'K', I would have had to choose between other possibilities such as POKE.
There's also the opposite problem of very large words. If you get an eight letter word, you only get 4 strikes... it's really not that hard to fail an eight letter word in the game

.
To sum it up, my problem with the game and why I no longer play is that I don't like the fact that you tend to guess more than anything, which means for the most part... there's very little skill involved. I hate winning mostly by luck :|. It's a shallow victory!
I was thinking of getting Gameloft's Eternal Legacy HD, it is on sale for 99 cents
I have it and it's an alright game. I'd recommend you turn the voice acting off (it's pretty bad), and the one thing I don't like about the game is that you cannot control your entire party during combat. If I remember correctly, you tell them to behave in a certain manner and they will act that way while you control the main character. I think Final Fantasy XII was similar in this way?
Personally, I thought Square-Enix's Chaos Rings, while quite repetitive, was a better game overall. Unfortunately, Chaos Rings is also considerably more expensive as the cheapest it's gone was.... $6.99 (iPad) I believe. Chaos Rings also needs a ton of tuning to make it a better game. In the end, an enemy my level could usually never hurt me (literally dealt 0 damage or I dodged/resisted). I also healed for 5% of my HP (automatically) after each turn. Earlier in the game, I ran into these mobs called Salamanders that could two shot me when they were my own level :\. It really sucked when I got a surprise attack (they go first) with two of them.