The compromise position is probably to only have overhead bin space in premium cabins, then the price of overhead bin space is folded into the premium ticket.

Good point that carry-on bags probably also slows down security, and the amount that it slows security down is probably not negligible. Without carry-on suitcases, you could probably completely do away with the X-ray machines (hand-check people's purses and backpacks), which are (anecdotally) probably the biggest bottleneck at airport security.