Another option is USAA. Unlike their insurance, you don't have to be a member of the military to use their banking services. They are an online-only bank and have magnificent customer service. I switched to them from Wells Fargo a few years back and can't recommend them enough.
If you've ever used a banks website an thought to yourself "This is fucking retarded, who built this pile of shit" switch to USAA. If only for the superior web presence, it's the best thing ever.
I switched to USAA too. Overall I've been happy, but I must admit it's a pain in the butt to get money in there. The only easy way to get money there is direct deposit.
If they'd fix that somehow, it would be fantastic.
You can take a check to a UPS store[1]. If you're a customer of their car insurance, you can also deposit checks directly by taking a picture of them with your phone via their app[2] - I realize that's not accessible to many folks though.
