I think the concern about block template construction is perhaps a bit too narrow. It is a complication on itself, and it gets worse as transaction sizes approach the block size, but it doesn’t need too much hand-waving to assume software can be developed that can do block template building near-optimally given a reasonable pool of candidate transactions, and made available to anyone to use in mining operations. I think it would be far better if this was not needed, but there is a much more serious related issue.
The issue, as I see it, is that as block template building for miners becomes more complex, reasoning by relay nodes (who possibly do not mine) about profitability becomes harder too, and far more so than actual block building, because it is a decision that needs to be made ahead of time, possibly long before the transaction might make it into a block, while other intervening transactions may arrive between relay and the block being found. Without information about miner-incentive-compatibility at relay time, and barring trivially-DoSable “just relay everything” policies, an honest user who wishes to use giant transactions will not be able to rely on the public P2P network and anonymous miners to get the transaction confirmed anyway. And without the ability to rely on this, these users will be forced to make agreements with mining businesses anyway to get guaranteed block space. The goal of any proposal to deal with giant transactions must be to make users able to get their giant transactions confirmed, without private agreements with miners, and without significant extra cost. If a proposal fails at this, it does not matter how good block building available to the common denominator of miners is, because users and miners will bypass all of that anyway.
To illustrate this problem, first consider a (intentionally unrealistically) extreme example: a user who wants a consensus-valid 999800 vB transaction to be confirmed. This is a legal size, in that consensus-valid blocks could exist that contain such a transaction. But due the size of a block header plus the minimum size of a coinbase transaction that includes a witness commitment, no miner will ever include it without a private agreement, as it would require them to burn all block income: there is no space for any secure normal transaction output in the coinbase anymore. That is no problem if the user pays the miner out of band for an amount above the displaced income they would get from the block otherwise, but I don’t see how it could be done in a manner that only uses the public network.
Okay, so we do need some limit on transaction sizes below that value, but how much? For exposition purposes, assume a hypothetical consensus limit of 990000 vB on transactions, assuming that no header+coinbase will realistically want to exceed 10000 vB. Does this solve our problem? Imagine this transaction pays a feerate that places it 20000 vB away from the top of the mempool (i.e., there exist 20000 vB worth of transactions that pay more). For DoS purposes (including relay rate limiting, RBF, and eviction decisions), the giant transaction will be treated as being better than all mempool transactions with lower feerate (possibly after chunking, though we can ignore that effect for the purpose of this discussion, as long as the giant transaction itself does not have big dependencies, or involved in CPFPs), including the 980000 vB worth of transactions that follow it. However, due to bin-packing effects, it may well be the case - even to an optimal knapsack solver - that this transaction stays outside of the optimal block template for a long time, or it may not be the case. It depends on the steepness of the fee-size diagram in the 10000 vB before it. This can result in bad relay decisions, bad replacement decisions, opening up the network to free relay attacks, transactions staying in the mempool which realistically won’t actually be mined, and in the other direction if it happens closer to the bottom of the mempool, transactions which may be evicted despite being fairly reasonable for inclusion later. This effect is much less for small transactions, as they generally need a much bigger mempool change to be bumped to the next/previous block.
In short: for small transactions, mining quality is a static decision that can be made once (e.g. at relay time). The larger a transaction gets, the more its mining quality will depend on other transactions available at block finding time. Uncertainty about these means that reasoning for DoS purposes breaks down.
I’m not convinced about the approach suggested here - it feels like it should lead to similar problems still, but thinking practically I can’t really see many issues. At least the “only 1 large transaction + coinbase in a block” rule is effectively equivalent to “treat every transaction as if it had ~1 MvB in size”, block building becomes “try normal block building, only considering non-giant transactions, and compare the fee of that with the highest absolute fee giant transaction”. For everything else, the giant transaction looks like it can pretty much be treated as having tx.fee / 1 MvB as feerate. Due to only one transaction fitting in a block, CPFP and other dependency issues are largely gone. Pinning might be a problem, but only if those who need such transactions require replaceability in adverserial settings.
(thanks to @sdaftuar for discussing this offline)