I have to ask, are you familiar with Tent? (https://tent.io) You just described exactly what they are setting out to do (and on a basic, somewhat limited level, already do).
I agree the effort faces serious challenges, but as I hoped to illustrate with my email analogy, it doesn't require every user to set up their own server to benefit. You could choose between keeping your data with a hypothetical GTent, or Yahoo! Tent, or Fasttent.fm, whichever one had the best policies, ad-supported or, if you prefer, paid.
Imagine I have a thousand friends on a distributed Facebook-clone. I post a photo, and that instantly gets pushed to anywhere up to one thousand different servers. Every server has to store a copy and index it. If that was a 1MB image, I just pushed a solid gigabyte of data out. Pushing an album of 50 photos pushes that to 50GB, or 5% of my dedicated servers allocated bandwidth for one users photo album.
There's no way an individual or group is going to be able to host their own servers. The whole system just dissolves down to a single large provider serving the vast majority of people, and we're back to Facebook again.
It's a great idea when you sketch it out on paper, but it becomes impractical very rapidly.
Now when you get into the millions of followers, like Lady GaGa has, your complaint is a valid one for textual posts (which are pushed in full). But at that scale, privacy clearly isn't an issue, right? I don't see much use for saying "these 3 million people can see my post, but hide it from everyone else". And if the posts are public, you can use a model like PubSubHubbub's to ease load on the origin server. Tent doesn't have that kind of feature yet, but I imagine they'll cross that bridge when they come to it.
I also disagree with this reasoning:
> There's no way an individual or group is going to be able to host their own servers. The whole system just dissolves down to a single large provider serving the vast majority of people, and we're back to Facebook again.
The first sentence is, in most cases, true, just like most of us don't host our own email servers. There's a substantial economy of scale with email. But can you name me one example of a "single large provider" that monopolizes hosting an open protocol? I can't think of one. With email, we have three large providers (Gmail, Yahoo! and Hotmail together serve ~80% of US users), and we also have a number of small providers. That means you have a choice.
However e-mail providers seem to manage quite nicely.
There's also no need to push it "everywhere": There's no reason why a decentralized solution can not have actors that act as hubs either for end users, or for smaller hubs, and get their margins either by reducing the fan-out or by being able to get sufficient size to benefit from peering arrangements to bring costs down.
Even a system that somehow mandated such an arrangement and where it was impossible to be part of the "inner circle" without a very substantial number of users in order to keep the message fan-out in check would still be a vast improvement over having "just Facebook".
The most important aspect from a user point of view is to have the option of moving elsewhere, not whether or not it is cost effective for a user to host everything themselves.
(And there's no need to instantly push out every image and have all the servers store each image - push links, and have the clients cache and/or archive based on criteria they care about).