We could go on and on about all the games featured below, but let's face it, you'll probably stop listening after you see the word Carcassonne. Yes, Carcassonne is out for the iPod Touch, iPhone and iPad, so you can play it in-between times that you'd probably be playing it anyway.
Carcassonne - The extraordinarily popular board game makes its way to the iTunes App Store, and all it lost in the 
transition was a bit of paper. Play against friends or against the computer AI (or complete solo games and challenge friends to beat your score) as you take turns placing tiles that form the walled medieval city of Carcassonne. After a tile has been placed, you can occupy one of its features (road, field, city, or cloister) with a person. There's a tutorial that walks you through all of this, so if you're a Carcassonne newbie, you'll be just fine. The game is remarkably faithful to the original, which fans will appreciate, and the interface is smooth and easy to use. A perfect adaptation!
Sigma - If you enjoyed Unify (and you really, really should have), Sigma will get your brain going in much the same way. Two cylinders of tiles face each other from either side of the screen. Use your fingers to rotate the shapes and tap the screen to send the middle block to the other side. Make matches of three or more and you'll chisel away at the cylinders and eventually progress to more difficult levels. Great design, smooth gameplay, and a colorblind mode makes things especially friendly for all players.
THINK - Brain training games are still popular with mobile gamers, and THINK is a solid entry in that genre. Complete challenges in four categories (reckon, comprehend, memorize, think), each with its own set of games and puzzles to complete. Best your own scores in the daily test to see how good you are at each one. Simple design that does an excellent job showcasing the brain teasers!
NOTE: Games listed may not be available outside of North America. Prices are subject to change and are therefore unlisted. Please see the individual game pages for purchasing info.
I bought Carcassonne on the iPad - its just the iPhone version right now, but apparently the HD update will be free for existing owners and a price hike for others. Not a disappointment. Even with the rescaled interface the graphics look great, the game plays well and the spoken tutorials are really helpful.
One minor nit: as a beginner it would be useful to have some way of stepping through the end-game scoring.
I have Carcassonne the board game. I don't have an I-phone :(.But I can tell you this, if you don't know how to play I recommend that you look at the tutorial first. It a very fun game once you know how to play.
I also play on the iPad and you almost can't even tell it's just the iPhone version running at 2x size. The extra screen room comes in handy as the play area gets larger from all the tiles.
As for scoring, I agree that the scoring can be confusing for beginners. It would be nice to see a detailed listing of each score made throughout the game.
I recommend that you play several games locally with some computer opponents to get the hang of things. You should pick up on the scoring fairly quickly that way.
Update