For a game, Cube is a great open source doom clone. Bit big though, probably for ipods.
OperaUSB is already out (and ten megabytes smaller than firefox...), I'm not sure if this site will ever collaberate with that, but it is pretty cool, just not easy to find.
VLC is a media player
Space mongler is a classic utility that lets you see filesizes graphically