Definitely worth downloading the free version of Angry Birds to see if you like it. I’m one of those who doesn’t seem to have the right gene to appreciate this game, but it’s undeniably popular with a lot of folks. Doodle God is another one that seems to be popular (though not mentioned here yet) that I find incredibly dull and tedious after about 10 minutes, but has incredible ratings (4.5 of 5.) Play the online version here to see if you like it.
If you like backgammon, Backgammon NJ plays an extremely competitive game (I can only consistently beat it through the medium level, and there’s hard and expert levels above it), and will rate your overall play based on its deep analysis of game positions. It will also give you a running total (if you want) of who has the positional advantage throughout the game. If you play backgammon as seriously as chess, this is the iPhone backgammon app for you.
If you like word games, Bookworm is a fun word-based game from Popcap, creators of Bejeweled.
I, too, am curious to see what else is out there. Except for Backgammon NJ, I haven’t found any games I’d rate 5/5.