Trainyard - indeed a sweet puzzle game, very well made and not generic. The free "lite" version called
Trainyard Express is even more than just a demo, as it features 60 unique levels which also take a while to complete.
Pew Pew (2) - a great creative "arena shooter", similar to but different from Geometry Wars. Highly polished and well thought-out with several distinct modes. The first Pew Pew is free and now serves as the test version for the second one, but is still well worth playing
Tilt to Live - somewhat similar to Pew Pew, but entirely tilt controlled, extremely polished and also very imaginative
Solomon's Boneyard - a more arcade version of the Diablo-like Solomon's Keep, similar to Crimsonland and the likes. Choose one of the 4 (+3 unlockable) unique wizards, survive hordes of enemies, level up, and collect gold to spend on upgrades which count for all matches, kind of like the upgrade system in Desktop Dungeons. Not very unique, but I found to be highly fun and addictive
Doomsday: Hellraiser - Doom clone based on
Freedoom. From what I've seen it's technically identical to the official Doom Classic for iPhone, but it's cheap and also very nice. Especially the controls are just superb once you get used to them
HacX - also very similar to Doom Classic, but a conversion of an old commercial Doom clone and free. As with Doomsday, great controls, fun!
Hoggy - haven't played it much, but it seemed to be very much inspired by VVVVVV, with the same gravity changing mechanic, but lighter, more colourful, and free
Generally, it's worth to occasionally look on AppShopper.com for popular free games of the day here:
http://appshopper.com/iphone/games/free/A lot of terrible games still show up there, but every once in a while you'll come across a free gem.