How would I go about enabling users to add files when creating a case? Ideally I would like the user to be able to select New case and then when they are populating the case have an option for adding one or more files to the case. (I should highlight that I don't want to provide alternative options such as email2case etc.)
The default "new/edit" page layout of any sObject does not support the upload of an attachment.
I suspect the user flow is as it is largely because in order to connect the attachment to the record, you need an id in the first place. So once saved, you then add the attachment. Or, in Summer 14, you post to the Chatter record, which automatically adds files as record attachments.
To do what you want to do would require customizing the UI with Visualforce and a custom Apex controller extension using standard controller.
You could then override the "new" action of the Case object to use this Visualforce page instead of the default page layout.
As file upload with Visualforce to attachment is a fairly common customization, I would check developer.salesforce.com for some guidance on how to implement this.
There are several existing questions on SFSE that could also give you an idea of how to tackle this, such as this one.