First off is, does this audit need to be legally binding?
Do you need to stand in a court of law and unequivocally say, Person X did actions, A,B,C and I can 100% guarantee that information?
If so, well then what you want is an appliance to do the auditing for you, Imperva, Guardium etc, it must sit in-between the network and the DB server. DON'T get auditing software, it must be an appliance and it must be controlled via your security teams, not the DBAs.
Secondly how tamper proof does the audit need to be, anyone with enough rights can stop a SQL Audit, do what they want to do, enable the audit. Anyone with rights to the path/UNC that the sqlaudit file is written to, can again tamper with the files.
For that you may want a software like Idera SQL Audit, which is again controlled via security but its not fully legally binding as an appliance would be.
Thirdly, who is actually going to be looking at this data? What tools do you have like syslog servers, splunk etc etc, as you're going to be generating thousands of events, whos going to be taking the sqlaudit file, parsing it and reading it or whos going to be taking the security Windows log and parsing it and reading it.
As for overhead, yes there is going to be overhead, as with anything there is overhead, how much is going to drastically depend on your workload, but expect a rough 1%-5% additional load, also you need to ensure whatever your writing the audit data too can keep up with the amount being written to it. If going to the security log, how quick is it rolling over, can syslog/splunk keep up with the amount of churn as you're security log is limited on size so if your churning more than syslog can read you'll lose events.