I guess link-local addressing is just broken on Linux.

There is not clear, unambiguous instructions for setting it up, but I just followed the same instructions you'd use for setting up a private network, and Linux would not even correctly assign the address. When I manually assigned the address, something made the address disappear.

So, I set up a dhcp server.

Everything works perfectly now.