Audiosurf just may be the best rhythm game ever created.
Go to the site and sign up for the beta. Trust me.
As a game it has a mix of both timing and puzzle challenges, your speed is determined by the music tempo, you collect colored blocks that fill gauges and you try to grab three blocks of the same color (in a column or row).
The design is simple yet clever, with very small tweaks altering the gameplay significantly. Not only that, but they had the foresight to include a casual mode, where the puzzle element is gone and you merely have to ride along and collect blocks - or just ride along, if the mood strikes.
This game would be perfect for the iPod.