Bitt,
I have a USAA Four-Star checking account, I've had it for over a decade. The interest received is a joke, but ATM fee rebates of up to 10 transactions or $15/month is great (used to be $10/month but it went up).

I never make cash deposits, but the mail deposit envelopes are postage pre-paid, which is nice.

The minimum balance of Four-Star is either $500 or $1000, so that may dissuade you. I've been very happy with all of USAA's services - I have their credit card, this checking account, their car and home insurance (at one point renter's insurance) and soon I'll have a mortgage with them.

I can't think of a single bad experience with them in all this time. They answer the phone promptly and have the training to help you, and they don't use foreign call centers.

-Zeke