I mean, don't 99% of businesses that take one take the other?

I cannot remember where it was, but I have encountered a couple of merchants who accepted Visa but not MasterCard. Very rare though. Visa branding (Carte Bleue) seems much more prevelant in France than MC though.

Also, if I use one of the debit cards to make a purchase rather than an ATM withdrawal, is there any surcharge for that?

Not sure about USAA, but when you use your BofA debit card overseas to make a purchase, you will incur the forex transaction fee - 3% I think. You won't pay this to withdraw cash at an ATM, but you will anywhere else.