The OP wrote:
There aren't any decentralized alternatives to Facebook, Google, or Twitter because nobody's been able to ship one.

Well, that's what my company's been working to change. We started a little earlier than the Diaspora project was announced. And we've already designed the whole platform and built over 95% of it. As for the list, we have slightly different priorities.

#1 - we are putting this way lower on the list, and consider it unnecessary if the network is really distributed. Just like Google Plus's "Real Name Requirement" is unnecessary because if Bill Gates doesn't want me to see his real name, he doesn't want me to find his account via that name. It's more to enrich Google than to help people. The current IP system and DNS / Certificate Authority system can a good compromise for this, and notably they rely on centralized, albeit, delegated, mechanisms. One could argue that acquiring a domain can be completely decentralized in order to prevent censorship. But none of that is required for real time point-to-point connectivity, because with total privacy, you won't find the node you're looking for unless you follow a path through the network by which it wants to be found. All the nodes in that path would have to be online as you navigate them, but that's about it. I'll call this requirement #1a.

#2 - Absolutely. This would probably be shifted to #1 for us. For example, if I am on NYU's network and I friended a few people, and then I go join Columbia's network, it should seamlessly reconstruct my social graph there from the people who are also on Columbia AND want me to know that. Requests for information published by multiple parties would have to be routed correctly and responses would have to be combined. And so forth.

#3 - For you this is part of #2, but also assumes #1. Of course, to accomplish this, two nodes sharing a session would simply need to agree at all times to use one (or more) other nodes which are currently online, to pick up the session. If your device goes out of range of your WiFi and switches to some other network, it still contains the routing information for that node. This is a bit different in that it doesn't require #1, but only #1a.

#4 - I guess I do not need to worry so much about lower protocol levels, but basically if you can assume https, then that's enough (although you are at the mercy of the certificate authorities until TLS starts to use Web of Trust instead of x.509). Usually, people run clients instead of servers, and they choose to trust some server to run an application. Presumably this server would not be blocked by its internet service provider -- in fact it may be a wifi hotspot in an african village that doesn't even have internet. It would be a single source of failure, but only for that subnetwork. In a distributed social platform, one could easily just go use another server hosting the same app.

#5 - Private, encrypted, secure communication gets tough for some applications. For example, multi user chat or mental poker where you may not trust other participants. So until we have zero-trust technology for everything, people trusting a server of their choice seems to be a good general solution. And all this communication once again relies first on a reliable identity for users, apps, servers, etc. which can of course be achieved by self-signed certificates, but needs to be more seamless across networks as per #2.

#6 - Everything I've described above can be decentralized in the same sense the internet is -- smaller networks joining into larger ones. But you don't really need a central DNS, you don't really need a centralized identity. I also assumed you did, until February of this year when I met with Albert Wegner from Union Square Ventures. Our system was already able to handle everything as decentralized, but we wanted to have unique ids for every user in SOME database. Then we realized that this isn't necessary.

That said, there is one problem with the web's security model that does not allow apps to truly be decentralized. The problem is that, if I sign in using one app somewhere, and then visit another app, the other app doesn't know where I've signed in or which account I prefer to use. People attempted to solve it with proposals like xAuth which are merely stopgap measures ... but to date, no one has really been able to make identity totally seamless because of it.

In short ... I now disagree that #1 should be the biggest priority, because every doesn't REALLY need to be able to connect to every other node on demand, but only to nodes it has encountered while using the network. That makes everything able to be distributed.

As for the CAP theorem, I guess the reason you can't maximize Availability and Consistency while at the same time having Partition Tolerance is because subnetworks can disconnect at any time, and if you need consistency you'll have to wait for them to reconnect. But many problems do not require consistency across the WHOLE system! That's why we've chosen to extend the web model, where clients connect to a server they trust, and this can be used to power chatrooms and other group activities. Partition Tolerance within this subnetwork is only limited to splits within the subnetwork, not outside of it. And since the network consists of very few nodes compared to the whole world, the splits happen rarely, and the rest of the time, we can have high Availability while preserving total Consistency.