I know this sounds as bad as the slowing down blocks suggestion.  But an alternative would be to make miners pay higher fees for larger blocks.  An increasing haircut on transaction fees related to block size.  

e.g. 1MB block 0% haircut, 10MB block 10% haircut, 1000MB block 95% haircut.  Some polynomial could determine the formulae.

This would create a marginal cost of including more transactions in blocks.  The problem with this might be that the extra marginal cost doesn't differ enough for different miners on the mining cost curve.