Best way to organize lots and lots of media files?

In my experience, the best organization structures become stale eventually. With the amount of data you're talking about, I wouldn't bother trying to keep it organized manually, rather I'd install Google Desktop and just search for what you are interested in. It's a bit of a resource hog, but as long as you have the spare cycles, it does an excellent job indexing. Interface is familiar and would give you the thumbnail look you're looking for when doing an image search.

To organize my media files (mostly music CD/DVDs) i use Media Catalog Studio. It obtains many useful features, allows to sort files, see statistics, quick search etc.