If there is one thing I love to put on any PDA I've owned it's puzzle games. They're great for when you have a few moments of spare time (i.e. your spouse is shopping and you've been dragged along, or you're on public transit). These puzzle games keep your mind sharp and they're fun. All these applications are free from the Apple store. (There are lots of others, but these are the ones I enjoy):
A great remake of the old Artillery game, but with way better graphics and multiple targets.
The classic Towers of Hanoi game, with great effects and graphics. Goes all the way up to 6 plates.
Moonlight Mahjong Lite
A great little Mahjong game, allowing you to view the board anyway you like.
You might know this game as Reversi or Othello. A great game with several different levels.
Try to just level one peg on the board. This could keep you busy for hours.
Sol Free Solitaire
Various Solitaire card games.
A great math game where you determine if the equations are true or false. Your score is based on time to solve all the questions, with penalties for incorrect answers.
A bit hard to describe, but something similar to Tetris. You eliminate groupings of pieces of a certain colour, with bigger bonuses for larger groups.
A remake of the Minesweeper. It only has one size at the moment, but it's very well done.
A puzzle game of lasers, mirrors and crystals. Very fun and addictive! So addictive you might just want to buy the full version, which thankfully is only a few bucks.
A card matching game to test your memory. It is timed to just to make it more challenging.
Arrange the numbered tiles 1-15 in sequential order.