Monkey Preschool Lunchbox (linked in the post) is solid (though I wish they would add new puzzles occasionally): https://market.android.com/details?id=com.thup.lunchbox&...

Zoodles works, though the quality of the games varies pretty dramatically.

My two-year-old asks every day to play Angry Birds. He's terrible at it (in the traditional sense), but he spends lots of time flinging the birds off in the wrong direction.

I'd second Zoodles. My daughter also enjoyed Toddler Lock when she was younger. Now she's five she enjoys doing Androidify pictures of me and my wife.

shameless plug of my app : https://market.android.com/details?id=in.microangels

Let me know if you have any suggestions for this.