One of the first really good free puzzle games I found for the iPod was flood-it (free iTunes download). It’s a simple concept. Your aim is to make all of the board one colour by changing the colour of one segment. For example if the first square is green, and the one next to it is red then you make the first square red and the blocks become a whole. On your next colour change any squares of that colour directly next to your block are added to the whole and it grows and grows.
I may not have explained it very well but it works very well, It’s also a good one handed “thumb” game. the only section of the screen you use is the six coloured circles at the bottom, and there’s no real speed. you can play it while walking around, or sitting on the bus and not worry about jostles and other issues.
It was also one of the first games available when I got my new G1 phone, and it’s just as addictive there. Some people have found it frustrating at higher levels but the easier levels are enough to keep me quiet.
The game is ad supported but there is a premium version available for the iPod for 79p (buy from iTunes), which I bought having spent so much time playing the free version. The pay-for version allows you to undo a move, upload online scores, retry a board, etc. Of all of these features I only really find the undo useful and it’s a pity that it doesn’t import the play history form the free version.
If you’re looking for a simple but deep strategy game to while away a couple of minutes (or even a couple of hours, then this comes highly recommend.