You don't need to store the entire block chain in every client, even in a model where you don't want to trust a third party server. Most of the block chain is "dead," in that the coins in those transactions have changed hands since then. You can drop those transactions as they can't affect anything. Further, since the block chain contains a Merkle tree, each client only needs to have log(n) blocks on hand to validate the entire tree (i.e., provided by someone else or federated across the network).

There's a lot of compression possible that the client hasn't bothered with yet. The community expects this to eventually be a solved problem.