Getting your certificates from on-prem to O365 for users is a manual process, and probably always will be a manual process, unless you are using Azure AD Connect (formerly DirSync), as discussed on SW.
Once a user has their certificate in their local user certificate store on their computer (done via group policy AutoEnrollment), you will always need to go into the Outlook properties to select the correct certificate(s) for signing and encryption, as you already know. After that, the only way to get it to Office 365 for that user, is to hit the "publish to GAL" button there in those Outlook options where you select the certificate.
If you revoke a certificate, which I should question why it happens so frequently that it's causing you extra work, and you distribute a new one, the user (or someone in IT) will just need to go into Outlook and select the new certificate. Surely you have an easy how-to on your Intranet showing users how to do it... basically just choosing the newest one available, then hitting the publish to GAL button. (kind of the same thing if one expires)
It sounds possible that there's a way to grab the cert data from AD and push it to O365 via powershell. It's probably just a matter of knowing how to arrange the data properly for O365 to take it. I'd submit a ticket to Microsoft via their O365 Admin portal. Surely they will have more info than me.
As for your Mac users, if they do not have a domain account or a certificate on a Windows computer, you can create a Certificate for them, export it, email it to them. Then they can install it on their Mac device via Outlook for Mac. I have a separate template set up for the purpose of creating external user certificates that are outside the scope of our domain, via CertSrv (hosted on your IIS server).
*** I re-read your first paragraph (after writing all of the above), and I am now looking at it a different way. Do you mean that the only way for someone to be able to send signed emails is if everyone in the entire company FIRST sends them a signed email or something? And then everyone needs to add that person in outlook? Now sure what you mean there, but I'm sticking with all the above I wrote anyways, as that's the standard. ***