For me, roguelike games are an absolute must have on any self-respecting games platform, and you don't get much more roguelike than, well, Rogue.
Rejoice, for Rogue has been ported to the iPhone and is available from the App Store right now. Go and play it - it is fun and free. This implementation has both primitive graphics and old-school ASCII modes (just rotate the screen to switch) pinch-zooming and (optional) gesture based commands.
If you like Rogue, though, you need to try NetHack. There is an iPhone port, but it requires a Jailbroken phone. License incompatibilities seem to be the main issue with getting the game on the App Store - does anyone know if there is an 'official' port on the way?
Rogue - classic Unix game comes to the iPhone [Gandreas.com via Touch Arcade]