This is a cool idea, but doesn't it generate some perverse incentives? If I'm running a full node and I want to pay CheapAir for some plane tickets, I'll want to pay in the greatest number of individual transactions possible

Peers can calculate rewards based on number of inputs or total kb used: you're paying for kilobytes with either coin age or fees no matter what. So I think in practice it's not a big deal.