From the perspective of a company with hundreds of employees each spending $20k/month - this is effectively a $2mm+ interest free 30 day loan from the credit card company.
Credit Cards take all the fraud risk. If someone fraudulently uses my credit card number, I am not on the hook for any charges. In Canada, at least, the consumer takes the fraud risk for a debit card. (Actually, for Chip+Pin Credit cards, last time I checked, they were trying to get consumers to take the fraud risk as well - not sure if that went through).
Lots of hotels want a credit card, not cash, when you are checking in. Some of then require a credit card, both for reservation, and your stay. I believe that the vast majority of car-rentals require credit cards.
Credit cards in the United States are an effective mechanism for young people to jump start their FICO score, which is important if they ever want to get a loan to purchase a home, (I'm presuming you see the advantage of buying a home with Debt).
Credit Cards, between points and various plans, provide 1-2% cash back on your purchases.
I can load my Credit Card onto my iPhone. I don't know if it's possible to do that with a Debit Card.
Here in Singapore, OCBC will give me an extra 1% on my savings account with their bank (up to $60K - so, $600/year) if I spend $1000/month on my credit card. (And 1% cash back on said card for all expenses.)
With that said - different places have different culture. Here in Singapore, Lots of Taxi's (all of them?) won't take Visa Credit cards, and around half of them won't take any credit cards. Lots of places (all the hawkers that I've run into) are cash only. In West-Coast Canada, Debit-Cards seem to be pretty popular.
But, Net-Net, outside of some of those use cases - I totally agree with you. I don't really see the fascination with credit cards either, particularly now that Visa+Debit cards+Chip+Pin+Smart Phones seem to offer a lot of the advantages of Credit Cards.