Make baking more efficient by forcing all subsets of the mempool to be valid
TL;DR the most pressing action item is to amend the protocol to prevent the creation of code carrying, spendable, KT1 addresses. The rest of the changes can follow.

As far as the mempool and the baker are concerned, an operation is valid or invalid solely based on its ability to pay its advertised fee to the baker. Erroneous transactions, computations going over the gas limit etc are all valid transaction which result in a NO-OP and in the fee being paid to the baker.

The mempool represents a list of valid transaction. Sub-lists of this mempool are not, in general, valid. This is because a transaction could hinder another transaction's ability to pay the baker fee. While such dependencies could be rare, they need to be guarded against and yield a relatively inefficient baker.

A solution would be to impose in the mempool that the fees required to pay for a manager operation must be available to the manager, irrespective of any credit that might be received through the consequences of other transactions in the mempool.

One solution would be to evaluate the validity of each manager operation in the mempool independently, as if it were the only operation in the mempool. However, we would also have to prevent a given manager from making several transactions in one mempool. This effectively limits every manager to a single operation per block. This is not a huge limitation as manager operations can be bundled. It might however, change the abstraction model currently used to manage the mempool.

This solution breaks down in one case: if a manager operation spends from a KT1 address, it could be that another transaction previously emptied that account through a smart-contract. Therefore, a further restriction is that KT1 accounts would become unspendable, i.e. managers would no longer be able to sign operations sourced from a KT1 account.

In order to migrate the existing system, I would propose that

Unspendable KT1 addresses with code are left as is, yay!

tz1 addresses now be given an option to delegate. This will also simplify matters for wallets.

Spendable KT1 addresses with no code can be marked as deprecated and require their manager to migrate their funds off of them completely as the only valid transaction.

Spendable KT1 addresses with code are more problematic. Their michelson could be amended automatically to allow for manager operations, but that might break another contract trying to call them... If this was phased in alongside multiple entrypoint for contracts, the disruption would be minimal.

If this plan is to be implemented at some point, and I think it should, it's important to minimize category 4. Thus, as an immediate step, I would recommend preventing the creation of code-carrying spendable KT1 addresses as soon as possible since they are the thorniest case for migration.