I am still wrangling with the data on the stateless client, to complete my post, but I would propose (in the 4th version of State fees/rent proposal) to only introduce stateless clients approach for contract storage items. I am currently missing data on whether size of the block proofs (witnesses) for contract storage eventually overtook the block proof for accounts and for the code size, because at the block 5.4m those 3 components were roughly on par. That is it to say, that byte codes played significant part in the block proof, and increasing contract sizes can push it up even further.
Even if we were to go with the pagination approach, we need still look at the compilers to try to optimise the code so that the code of specific functions are partitioned well (i.e. usual function calls do not end up touching all the pages).
In general, I would approach this proposal with caution, and also in the context of other EIPs that propose to change EVM, most notable EIP-615. I would definitely welcome more research.
For example, it was noted that the code of the contract is inflated by the PUSHx opcodes storing data inline in the code. Perhaps, the solution to this is to use DATA segment approach that has been introduced into EIP-615?
Another point - some of the desire to put lots of code into a single contract stems from the fact that this code wishes to access the same storage, without calling wrapper contracts. Currently, it is very appealing, because reading storage (SLOAD) cots 200 gas, and any call to a wrapper adds an extra cost of 700 gas to that, so it ends up being 900. But the cost of SLOAD is likely to be increased 4x or 5x, because it is overpriced, so the relative win from co-locating the storage would decrease.