We are having trouble with autodiscovery on an Exchange 2013 server. Autodiscovery and outlook anywhere work, however we have a certificate error. The error is in regards to autodiscovery.domain.tld and domain.tld. How do we fix this without a wildcard certificate?

Hey there, 

While I may not get what you mean correctly, do pardon me if I get it wrongly.

This article may answer you: http://exchangeserverpro.com/exchange-2010-faq-autodiscover-names-ssl-certificate/

Therefore, yes, you would need SSL for your autodiscovery if the device can't establish a proper trust. 

Thanks.

Basically you need to make sure your clients trust the certificate that Exchange is using and all the names are on it.  You can certainly use an internal certificate, but when users connect to anything externally (like owa or active sync) they will get a cert error.  Here's a good blog that should give you some pointers on certificates and certificate planning in Exchange 2013.

http://blogs.technet.com/b/exchange/archive/2014/03/19/certificate-planning-in-exchange-2013.aspx