I ran into this issue with multiple domains with Exchange 2007 and 2013. We have 12 email domains that we support. Microsoft's stance is that they don't support "vanity" URL's meaning that the "Best Practice" is to assign a communications
domain per datacenter and then setup URL redirects in IIS that redirect autodiscover.domain1.com to autodiscover.CommunicationDomain.com. There are "Exchange Hosting" add-on's that extend the vanity URL support but those can be expensive
and overly complicated.
In response to the certificate question, probably the easiest option would be a SAN cert with all your email domain hosts assigned to it.
We transitioned from Forefront TMG to F5 Big IP and APM. The F5 gives us the ability to rewrite the autodiscover response XML file and replace the domain URL's so they match the users email domain. So a user on domain2.com gets all domain2.com
URL's in the autodiscover response and domain3.com users get domain3.com URL's. The F5 option is, of course, expensive as well.
To keep things simple I would probably go the route of SAN Certs and doing the IIS URL redirect. A good example of this in action would be Comcast business email service. You might have your email domain as Justino.com but in your account setup
in Outlook, your Exchange proxy URL is mail.srv1.Comcast.net.
Here's a link to this scenario for exchange 2010 but the same thing applies to 2013:
http://www.msexchange.org/articles-tutorials/exchange-server-2010/mobility-client-access/using-autodiscover-large-numbers-accepted-domains-part1.html