I'm going to keep encouraging people to try Pandamania. I just keep going back to that game, and I continue to have fun every time I play. And I've played it a lot. I'm number 2 in total score, and I keep going back to different levels to boost my high score. But it still hasn't gotten old for me. It looks and plays beautifully, has a good sense of humor, a wide range of different enemies that require a variety of strategies, challenge without frustration, weapon upgrades, boss fights, leader boards, and just lots of crazy action. I love it. It's up there with MiniSquadron as one of my favorite games. Meanwhile, I've been writing down titles from all the recommendations on this thread. There's so much good stuff on the AppStore that I might never find by myself, so thanks to all for the suggestions.
Land Air Sea Warfare! This game got completely looked over. It's probably my favorite RTS on the app store right now. It reminds me of the first Total Annihilation game on the PC.
Damn, I remember buying Pirate Wings when I still had my first gen touch. It had a really low framerate. How does it run on a 2g ipod touch? Also, KotH is really overlooked. It's pretty much Sentinel (if anyone else remembers that game).
Jyhjyh, by stating that 3-Duko needs more recognition, you have stumbled on to one of the best (or worse) kept secrets of the iTunes store. This groundbreaking app that puts Sudoku into the third dimension needs to be seen by the 500 million people who play Sudoku every day (worldwide stat). It's a revolutionary app by oBo Games and Secret 6. As it's creator, I thank you for the nod.