You can disable the "New Folder" button in
Library Settings -
Advanced Settings -
Make "New Folder" command available?. This does not stop a user from opening in explorer view and creating folder there, like you had mentioned.
As far as permissions on the library go, contribute to the library gives them access to create new documents as well as new folders. I don't think there is a way to have one over the other.
Looking through the permission levels you can see what SharePoint gives as list permissions as well. There's no differentiation between folders and documents from what I can see.