I went through this exact dilemma when I was relocating to California for my sabbatical. My normal bank, Chase, has no branches anywhere in CA and charges stupendous fees when using non-Chase ATMs.

I have my retirement investments with Fidelity, and they turned out to be pretty good as a bank as well (although the fees don't entirely disappear until you have a non-trivial amount of money invested). Fidelity gives me checks, an ATM card that forgives fees, and free Quicken downloads. They've got local branches in various places around the country. The only things they don't do are things involving cash. You can't walk up and ask for a roll of quarters.

I ended up joining the SRI Credit Union as well. (I'm splitting my sabbatical between SRI and Stanford.) The credit union has no minimum balances, gave me free checks, and also reimburses ATM fees. Plus, they've got a convenient branch office in the basement of the building where I work. They don't do Quicken downloads in any useful way, though. (They'll generate a QIF file, which Quicken knows how to import as a new account, but they don't generate a WebConnect file, which is what Quicken knows how to merge into an existing account.)

My suggestion is to take a closer look at any banking offerings made by whatever company you use for your investments and/or retirement. You may be pleasantly surprised.

On a deeper level, this whole monthly charge to download data is exceptionally annoying. All of these banks let you do everything from their web pages free, but they charge you for the same thing through Quicken. I think Intuit is part of the problem, trying to get a cut of the action. I suppose some banks might let you download OFX, which you should be able to import into Quicken or whatever else for free.

Has anybody tried Microsoft Money? The last thing I want to do is lock myself closer into Microsoft Windows, but it's certainly a viable alternative to Quicken. Then there's always Moneydance or Gnucash. It's not clear whether either one has all the Quicken features that I know and love.