Lync 2013 and external user connectivity

Sorry for writing big about the enabling public IM access for the Lync 2013.  Public IM will not work just by enabling it in the Lync server and enable access policies.  You must go through a provisioning process to activate. : https://pic.lync.com/provision/Logon/Logon.aspx?rret=https%3a%2f%2fpic.lync.com%2fprovision%2fAgreementNumber.aspx 

Provisioning with public IMs for MSN and AOL but i believe AOL have stopped it, for yahoo you need additional license. You need to activate those federation services using PIC.

Refer the link for the supported IMs
https://technet.microsoft.com/en-us/library/dn458579(v=ocs.15).aspx

You must also read this important article from Microsoft about the known issue for integrating the public IMs : https://support.microsoft.com/en-us/help/897567/known-issues-that-occur-with-public-instant-messaging-and-lync-server

Here is the step by steps : https://technet.microsoft.com/en-us/library/dn440174%28v=ocs.15%29.aspx?f=255&MSPPError=-2147217396

Also ensure you have Reverse Proxy server and secure as much you can on your edge, reverseproxy servers.

In addition to comment above I'll suggest to take a look at this article regarding Lync federation:
https://www.petri.com/setup-lync-federation

Say for instance a small company with domain name smallcompany.com uses Skype and doesn't have their own Lync setup.  To allow a company that has Lync 2013 setup to communicate with them, the domain smallcompany.com would just be added to federation?  Or would you need to federate with a Microsoft domain since that's what Skype uses?

Small company (using consumer skype) only needs to supply big company (with lync 2013) with their skype address(es).
Big company, with Lync 2013, is required to setup federation with skype (consumer). They need to do all the work.