Found the issue.
The DelayVirtualizationType registry key had not been set on the golden image for the RDSH Farm (as per the last line of Install App Volumes Agent )
So App Volumes wasn't fully mounting the applications until logon - as designed.
After setting the registry key and re-publishing the applications are getting properly mounted at start-up and Horizon is able to find them.
*Face-palm*