If you're looking for ideas, there's
shouldexist.org or
halfbakery.com. Try shouldexists first. A german site which lists software ideas is
here - just run this through an online translation service to read it.
I really like QTParted but I miss a GTK GUI - it doesn't make sense to install several big liberies to get on seldom needed tool running. But this is probably not what you are looking for.
Another idea is to bind all those email import filters at freashmeat into one mail-import libery. Some of those tools there do their job only partially so there's enought to do.
Additionally I heard that some ppl are looking for a mid-class photo manipulation programm - not as powerful as The GIMP, single window usage and good enought to care about some photos.
Another nice thing would be good-looking kernel creation tool (KDE and GTK if possible) which reads configuration possiblities of the installed kernel, lets you choose from nice trees with good hints, and has a button, at last, to build a distri package which can simply be installed. There's already one attempt to do this as far as I know but it looks bad (i saw this on kerneltrap, I believe). Since some ppl seem to have also some problems tweaking their harddrive, a nice GUI for that may be what you're looking for.
BTW, there's a lot of stuff missing concerning scientific software I believe (like SPSS, for example). There's R on the command line but I haven't seen a good looking GUI yet. I admit I didn't search for it.
Multimedia is also a nice point. AVIdemux is really cool but something like TMPGEnc is still needed I guess (a MPG Editor with GUI).
Something I found right now when looking at a "best freeware tools" page for windows was something called Preispiraten (pricepirates). It seems to be able to search in about 550 online stores and eBay to compare prices for specific products. It might be interesting to extends this functionality for online consumer rating sites.
Well, hopefully this was enought inspiration for the moment.
Edit: An interesting note when you look at such "Best Download" sites for Windows is: There's not much which isn't available on Linux! Some is unique to Windows (anti-virus, for example) and most missing seems to be easy-to-use DVD copy stuff.