There is still the question of what the default behavior should be. Here is a proposal:
Ignore blocks that take your node longer than N seconds to verify.
I'd propose that N be: 60 seconds if you are catching up with the blockchain. 5 seconds if you are all caught-up. But allow miners/merchants/users to easily change those defaults.
Rationale: we should use time-to-verify as the metric, because everything revolves around the 10-minutes-per-block constant.
Time-to-verify has the nice property of scaling as hardware gets more powerful. Miners will want to create blocks that take a reasonable amount of time to propagate through the network and verify, and will have to weigh "add more transactions to blocks" versus "if I add too many, my block will be ignored by more than half the network."
Time-to-verify also has the nice property of incentivizing miners to broadcast transactions instead of 'hoarding' them, because transactions that are broadcast before they are in a block make the block faster to verify (because of the signature cache). That is good for lots of reasons (early detection of potential double-spends and spreading out the verification work over time so there isn't a blizzard of CPU work that needs to be done every time a block is found, for example).
Using this proposal all nodes could select for themselves what block size they are willing to accept. The only part that is missing is to communicate this information to the rest of the network somehow.
Each node could keep track of the ratio of transaction size to verification time averaged over a suitable interval. Using that number it could calculate the maximum block size likely to meet the time constraint, and include that maximum block size in the version string it reports to other nodes. Then miners could make educated decisions about what size of blocks the rest of the network will accept.