I called up USAA and asked them about their checking account. Turns out that the interest that they pay is 0.15%. But, apparently, they do give you 0.5% cash back on purchases, which probably works out to being about the same for me. You can get overdraft into a USAA savings account (which pays up to about 4% interest, tops) or a USAA credit card. The deposit-by-scan thing requires that you have a USAA credit card. Otherwise, you have to mail it to them. They have no way to accept cash deposits, so you have to convert it to a money order and mail it in. I still didn't get really good information about the fees that they do have. Apparently "regular stuff". I did get a specific example of having a check returned when you don't have overdraft. (I really like ING Direct's "these are the only times we will charge you a fee" statement.)

To me, the ING Direct account sounds better, except for the ATM issue. The ATMs they have look like they're all inside businesses, which means that, in addition to feeling like a jerk for going in a store just to use their ATM, if the store is closed, you're out of luck.

I already opened an ING Direct account (it only cost me $0.51 in an initial deposit, minus whatever they're depositing in my checking account for verification). I'll at least play with it for a while and see how it goes.