Many things are difficult, but that shouldn't be difficult at all: miners just include transactions that pay the most (if space is limited) or that pay minimum X bits, X being defined by the miner, (if the space is not limited). THAT'S IT!
But what about when blocksize is too small that the fees become high lowering BTC's usefulness as a cheap payment system.
I am not in favor of artificially reducing the blocksize. But if the technology (storage space, propagation speed of blocks etc. similar factors) demands it, then I believe typical transaction fees in the $1-$2 range (50 times higher than now) won't kill it, ie. the Bitcoin's unique characteristics of a secure store-of-value ledger are unaffected even if the transactions were more expensive.