For puzzle games I'd recommend:
- Piczle Lines
- Marple (logic problems)
- Puzzle Quest 2 (basically Bejeweled RPG)
- Cut the Rope
- Sword and Poker
There are some good maze type games using the gyroscope, Labyrinth 2 HD is a good example.
Word puzzle games:
- WordFu+ (silly, but quite fun)
- Bookworm (tend to get bored before actually failing)
Solitaire City Deluxe is a very good collection of solitaire card games.
And games that pretty much everyone has: Angry Bird and Plants vs Zombies.
Some of the above are iPhone games which will play with pixel doubling on the iPad, this doesn't tend to matter too much with puzzle games.