Does anybody have any best practices for how to organise a folder structure?
Believe me, you don't want to own the folder hierarchy for any department (except maybe your own). You don't know what their needs are, don't have the knowledge or experience of other departments to make good choices, and don't want to be the company's file janitor.
And if you think they make a mess of it, that's nothing compared to the mess you'll make of things. I know you say you've been tasked with doing this, but the best thing you can do for yourself, is to get untasked from it, quick. This is an example of being set up to fail - no matter how you do it, someone is going to have a problem with it, and complain about or at you because of that.
The best practice is literally "[department head], here's your department share. You're responsible for structure and permission below this level. Set it up however best suits your needs."