Right so my dad got an iPad for some reason and so he's punted his iPod Touch over to me. This will be my fourth mp3 player so it's primarily going to be an app device (still lots of music, but 128 kbps for space considerations). These are all good suggestions! Here are a few more that I've found and liked.
100 Rogues - A Roguelike for the iPhone/Touch, with all the trappings of the genre - lots of challenge, swarms of enemies, and procedurally generated levels. There are two classes, the Crusader and the "Glass Cannon" mage (looks like there may be two more classes coming in updates). The two things that set it apart are its polished visuals (ASCII this ain't) and the tongue-in-cheek humor, which fits with the genre because it too is often punishing. There are reportedly some particularly rare "pranks" the game will play on you, such as the controls becoming unresponsive when surrounded by powerful enemies, or the game just up and quitting on you at inopportune times. Your ultimate objective is to kill Satan. Your character needs to eat to live but food is pretty scarce, etc. I'm pretty sure the developers have come out and said that you're not supposed to be able to beat the game, but beating the game isn't the point.
Simpsons Arcade - Remember the Streets of Rage-style Simpsons arcade game? It's back for the iPhone/Touch! Somewhat unfortunately the only playable character is Homer, but the game is still just as fun as you remembered it being. The controls are surprisingly responsive for a touchscreen.
Also Joe when is the ETA on your game?