I still havent found anything yet, but I'm stil looking.
I tried NextGen, but that doesnt let you use the media gallery items. I have looked at Catablog which is a nice simple solution, but only allows geaphic formats of jpg, gif and png which is ok, but I would like to add all types of media and not have to update it manually. WP-Filebase was another one I looked at which was similar that you have to add it manually.
In the end Attachments would probably be the best plugin as it lets you add any type of media and arrange them, but you have to manually code your template for this. Not a problem for me, but still not quite the solution I was after.
Something that just dumps anything from the media library into a template and updates dynamically.
I read something about WordPress 3.2 adding some new functionality to the library regarding adding galleries, but I am not sure what that is.
Anyway if you come up with anything or have any suggestions let me know.