In addition to all the good suggestions so far, I'd say that you should definitely look for a bank that is friendly towards small businesses and has good business banking products and services. Often times, you can get fee's waived if you have a good established relationship with the bank.
Once you've found a few banks your interested in, sit-down with a personal banker and have a conversation with them. Let them know that your shopping around and would like to see what they have to offer.
Once you've made your selection. Make sure you get some face-time in with the bank. Banks are risk-averse. Anything you can do to strengthen that relationship will lessen their risk aversion. Of course, if you are overdrawn on your account all the time, stalking your bank manager isn't going to make the situation any better.
Here are a few other factors I look for:
- FDIC insured, obviously
- Short-term liquidity products. Somewhere where I can park cash for day-to-day expenses
- Excessive fees (these can add up over time)
- Online cash-management and reporting tools
- Read the fine-print on "free checking". It's free for a reason.
- Avoid accounts that have limits and fees on daily transactions. (see previous point)