I have an idea, and guys, let me know if this is decent or crazy or whatever: or if this is already what is being done by JoinMarket, Shuffle, Whatever.
1. I make a website or a server for this purpose.
2. It asks users to create their transactions, and a given time limit, say 30 minutes or 1 hour.
3. Every 30 minutes, or every hour, it gets back to all the users with the giant CoinJoin transaction formed thus far and asks all the people to sign.
4. The site itself takes a fee, and that's some how inserted into the process.
5. Assuming the site is "trustable", then only outsiders are "attackers" and they're not going to learn much except "I see 100 inputs and 200 outputs, and I own 20 of them. I dunno who the other 80 are."
6. Repeat every hour or every whenever. Or every 100 people. Or once a day.
7. Java script or open source client side signing thingy that can sign for you if you're away from your computer so the site doesn't have to wait an hour when it reaches the minimum number of people.
I don't know if you're aware, but joinmarket exists (has done for a year on mainnet now), it's doing maybe 50-100 transactions per day (hard to get numbers without running the blockchain analysis mentioned above; and false positives there will confuse it). You can see the orderbook at
https://joinmarket.me/obAs for the description above, it's fine (it's the first, simplest design mentioned by gmaxwell in the OP) but having the server know all the linkages is a bit much. Joinmarket has one participant act as the coordinator for each transaction, and pay for the privilege of knowing the linkages for that transaction (I'm repeating myself now, I said this a few posts back). Instead of one server with a global history. To go further, you add Coinshuffle or blind signing so that no-one needs to know the linkages (assuming no Sybil case, i.e. other participants are really distinct).
The economic incentive, while small, helps create more participants. Most joinmarket coinjoins involve 3-6 participants although 10+ is not unheard of (I myself had a couple of 9,10 party joins recently, e.g. e701bc57fa663eaef4d57a9ea20b3212a90a8be71a32bd3bcb84062e864bdab0).