Simple to learn; anorexicably impossible to master? And no, I have no idea what 'anorexicably' means; it just sounds right.
How has only one person mentioned geoSpark?! What the F-prompt..anyways I'd definitely +1 geoSpark, its great. I could list quite a few games that meet your criteria, those tend to be my favorites But off the top of my head, if you like puzzlers, I'd say Unblock Me. That game has proven worthy, it keeps me coming back to play a few rounds.
I'm also in love with sweet little casual games with wonderful production value: Mr.AahH and Mr.Space are really cool. Music, graphics, concept - perfectly executed. And perhaps a little hidden gem: Das Cube Simple, very beautiful and still challenging. Enjoy.
MiniSquadron Peggle Dark Nebula Little Metal Ball Pac Man CE Lucky Coins (and most games from Donut Games) Alphabetic I have the lite version of Super Juicy and that seems to fit the bill as well.
To highlight two games that have not been mentioned, I would get Run! and Green Fingers. They are two of the games that I couldn't stop playing once I downloaded them, always trying to better my high score. Both have achievements and OpenFeint leaderboards.
Red Conquest... some people say the controls are difficult, but they are not! Play around in the first level for about 5 minutes, try everything you can find, then you will be ok. With online multiplayer coming at march it will be even better!
Minigore Labyrinth 2 BloodNGuns The Simpsons Arcade Tomena Sanner (idk, I like it... not too complex) Canabalt (only played the flash version but based on that, definetly fits)
get Running With Scissors: Pre-Season, is a running game combined with strategy. It costs $5 and has infinite replay value.
Wow!!! Thanks a lot! Im going to look through each and every app suggested! I didnt expected so many helpful responses! Thanks again!!!