I spend most of my time in either Virginia or Southern California and have found that Bank of America best meets my domestic checking needs. There's a B of A ATM on practically every other street corner in both places so withdrawals are easy. One of the few annoyances at B of A, however, is that I can only make ATM deposits in California, where I opened the account---in other states I have to go to a teller for deposits. B of A's online banking is also top-notch; I especially like the online bill pay and the ability to make instant payments to my B of A credit card.
I used to bank with Wachovia but now have a whopping $1.21 in that account; it's a basic free checking account, so thank goodness no minimum balance requirement. The main reason I left? Wachovia doesn't clear deposits (even CASH deposits...it's ludicrous) nearly as fast as B of A does, and I inadvertently racked up $120 in overdraft fees last summer when the bank inexplicably put a large paycheck on "hold" for a week after I deposited it. B of A credits $100 in available funds immediately, and the rest usually becomes available within a single day.
B of A charges $5 for off-network ATM withdrawals in foreign countries, so when traveling abroad I transfer some cash over to my PayPal account and use the PayPal debit card (the card is free, with only a $1 ATM transaction fee).
One trick to avoid ATM fees if you're traveling domestically: Most grocery store chains allow you to take out up to $100 cash back with a debit card purchase, so what I do is buy a bottle of water for 99 cents, pay with my ATM card, and ask for cash back. Works wonderfully, unless your bank charges a fee for PIN-based transactions, which B of A and Wachovia do not.