fun fact: In Germany it's exactly the other way round at least for 99% of the banks. You will get a free debit card at every bank but you have to put down a considerable amount of money as prepayment for a credit card additionally to the yearly fees. If you want a Deutsche Bank credit card they will lock 1000 EUR before they issue it to you and you will pay around 60-100 EUR yearly.
I think this holds for significant parts of the non-US world. In the Netherlands (and for that matter any European country I've visited) credit cards seem extremely uncommon. I am one of two people in my circle of acquaintances who owns a credit card and I only use it for buying stuff on-line (when no other option is available).
As I understand it you can also only get money from an ATM associated with your bank, making picking a bank an availability issue too. Here you can get money from an ATM not associated with your bank once every 24 hours, making ATM availability pretty much a non-issue.
