Regarding bandwidth requirements for stateless clients, I can give some precise numbers.

Currently, there are ~16M accounts, and tries have up to ~1M storage keys. Hence, a Merkle tree branch for a given account would have ~log16(16M) ~= 6.25 nodes, which corresponds to ~6.25 * 512 = 3200 bytes per account accessed (plus 100 bytes for the account declaration), and for a contract trie, the max is ~log16(1M) ~= 5m nodes, or ~5 * 512 = 2560 bytes per storage key (plus 32 bytes for the storage key). Additionally, an account can have a max of 24kb storage.

We can do two analyses: (i) simple transactions, and (ii) a worst-case DoS. In (i) we assume that every tx in a block is an A->B transfer. That’s 8m gas / 21000 gas per tx = 380 txs = 760 branches, 760 * 3300 = 2.5 MB. So an optimally running 20mbps connection can download it within one second.

In case (ii), we can look at three sub-cases: BALANCE calls, CALLs and SLOADs. For BALANCE, we have 3300 * 8m / 400 = 66,000,000 bytes. For CALL, we have (24000 + 3300) * 8m / 700 = 312,000,000 bytes. For SLOAD, we have 2592 * 8m / 200 = 103,680,000 bytes.

So it really doesn’t look good. So how do we improve it?

Here is what we would have to do:

1. Implement further, and very substantial, increases in gas costs for SLOAD, calls and BALANCE and similar opcodes. It will be necessary to implement an exception for self-calling and precompiles, perhaps only charge 100 gas for such calls.
2. Add a gas cost component that increases with code size. Perhaps, for example, CALL could cost 16000, but then refund 1 gas per 2 bytes by which contract size is *smaller* than 24000 bytes (eg. if contract size is 3000 bytes, refund 10500 gas).

But even then, we would lose heavily because the hexary trie is just not optimized for small Merkle branch sizes. If you replace the hexary trie wholesale with a binary trie, *then* the numbers become quite reasonable.