I have some experience of vfat, ext2 and reiserfs, and I've read about ext3. Here's my tuppenny's worth:
If you choose ext2 (or ext3, which is ext2 with an added hidden journel file) then you can choose the cluster (inode) size when you do the format. The lower the size, the less waste per file (but the bigger the inode tables; these should still be smaller than the FAT tables you've got now).
It will certainly perform a lot better than FAT32 if space is tight, because it doesn't suffer from so many problems with fragmentation.
ext2, ext3 and Reiserfs will all list files relatively quickly, owing to the fact that they store the filename (along with the file's meta-information) with the directory rather than the file itself. As I recall, so will nearly anything other than a FAT partition.
I would definitely tend to avoid FAT32, FAT16 and NTFS here (and tmpfs/romfs which store everything in memory!).
Go for ext2 in preference to ext3 or ReiserFS unless you want journelling support (i.e. must faster filesystem checks in the event of a crash or other forced unmount).
There may also be a specialist filesystem better suited to your needs. I'd be looking for something that stores files in segments rather than clusters if wasted space is really a problem.