Spirit Airlines actually has the right idea on this - you pay to bring an overhead bag aboard, and they mean business about it being the proper size. I'm able to get away with not checking a bag on the vast majority of my flights. I'm out of the airport like 5 minutes after I exit the plane.