We have the following configuration in our Exchange 2007 environment.

Webmail.company.com, and an existing certificate. 

We have purchased a new certificate with the following names;

Autodiscover.company.com

Legacy.company.com

I am stuck on how to configure Exchange 2013 with these two certificates.

I cant get Outlook clients to authenticate if their mailbox is on the 2013 server, and I need some guidance in getting  this to work.

New Certificate assigned to IIS--- with Autodiscover.company.com and a SAN of legacy.company.com, users get a certificate warning and then The Connection to Microsoft Exchange is unavailable.  Outlook must be online or connected to complete this action.  Outlook settings populate with the proper GUID of Exchange Server and Mailbox.

Webmail.company.com certificate assigned to IIS---users do not see a certificate warning  but still cannot connect to a mailbox on 2013.  The Connection to Microsoft Exchange is unavailable.  Outlook must be online or connected to complete this action.  Outlook settings populate with the proper GUID of Exchange Server and Mailbox.

Is it possible to maintain the webmail.company.com and the original certificate? 

Or should we choose a new URL for 2013, say  mail.company.com/owa  and obtain a new certificate with mail.company.com and two SANs for autodiscover and legacy?

Thank You

You need autodiscover and webmail in the same certificate.  Legacy can be in its own certificate since it's installed on the Exchange 2007 server and not the Exchange 2013 server.