> I don't know if there's an easy way to share keys in a decentralized way, but that'd be an interesting problem to solve (some blockchain maybe).
This is exactly what namecoin tried to solve. Buy an identifier, put whatever you want in it. Example: https://nameid.org/?name=rakoo
> The other question is whether we want server-to-server federation at all instead of a P2P network like bittorrent.
We want something in between. The best model I know is the one of scuttlebutt (http://scuttlebot.io/more/protocols/secure-scuttlebutt.html): Each peer is identified by an asymetric keypair, and writes posts/comments/photos to a local ledger. Everything is signed and potentially encrypted if the message is to be read only by select people. Diffusion follows the peers' connections: stuff is sent from peer to peer as they connect together, friends can be used as a third leg (ie a common friend can carry stuff even if it's not for them), and you also have pubs where more people can connect and get more stuff faster. This system is different from bittorrent in that everything depends on the human connections: information spreads along human acquaintances, names aren't globally unique, they depend on how your friends agree to name you, etc...
It's better than naive server-to-server federation because pubs can be simple, stupid message forwarders yet still have all the advantages of being always-up servers.