[guitarnick]

Can this be worked around with UX?

Show clear steps with images on the download page that direct them to click "More Info" to run the app. Eventually the app builds up reputation (at least until the cert expires). How effective would this approach be?

[bentcorner]

You can but you'd need to account for every OS/update combination to make sure you get the UX right. Many apps do something similar for teaching people how to click through the trust dialogs when running the installer when downloading with chrome/ie/edge/firefox/chrome-edge/etc.

Not impossible but it's definitely a hassle and probably non-trivial to get right.