That’s what I figured, but I thought I mention it anyway.
This is a tough one to troubleshoot, not having a device where you can reproduce it easily.
Without impacting your production site, I think that maybe you could compare User-Agents from both load-balancing deployments. If you can find a User-Agent that is present in the Ubuntu 16.04 logs, but is completely absent in the logs of the 18.04 deployment, we may have something we can work with (like an old Android or iOS release).
Other than that, blind fiddling with openssl (like compiling it with enable-weak-ssl-ciphers) could help with troubleshooting, but it’s quite “production unfriendly”, and requires to build openssl and haproxy manually.