I'll second the credit union idea. I finally ended up just going with the North Carolina State Employees' Credit Union, where I've had an account since I was little through my parents. I wish I'd done it sooner; it's a great bank. The people are universally helpful, they seem to go out of their way not to screw you, and any fees are minimal. (The exact opposite of my experience at Wachovia after First Union bought them and stole their name.)

I'd suggest looking for a credit union that really does restrict their membership. I also have an account with Coastal Federal Credit Union, where it's very easy to gain membership, and they're really impersonal and very corporate bank-like. Size doesn't seem to make any difference, though. NCSECU is actually the second largest credit union in the US, and far larger than CFCU. I think you just need to find one where the company culture remembers that you're an owner and not a customer.