So I successfully deployed Skype for Business 2015, registered our PIC at https://pic.lync.com, successfully ran Microsoft Remote Connectivity Analyzer at https://testconnectivity.microsoft.com/ (says it tests only Lync but works for SfB as well).
An internal Skype for Business Client can successfully search the public Skype directory and add Skype accounts. However, the 'We've sent a contact request." part of the screenshot below never happens. In fact, the Skype user never gets a contact request.
Also, Skype Users can't search for our federated Skype for Business accounts in the public Skype Directory.
So obviously I must have missed something while deploying SfB, but I can't figure out what. I double and tripple-checked every deployment guide I could come up with, nothing. Double-checked our firewall ACLs as well, all good.