I’ve used a plug-in called Publications Archive to do much of that. The only thing it won’t do is output a sidebar widget to show new downloads, but otherwise you can upload via the admin UI, categorize uploads, and create a nice, structured and styled list on a page.
Make sure you read the issues page to track down and fix any bugs. The plug-in hasn’t been officially supported for some time, so there might be a few tweaks here and there that you’ll need to do to get it to work. Eventually I’ll get around to re-writing the system to use custom post types … but that’s several months in the future.
You can see an example of the page output here. Like I said, you can have a structured, stylized list of the documents, files, etc that you’ve uploaded.