Unless Gale, or anyone else, has more ideas, I think we’ve covered all of the easy options. We can see that Audacity is crashing early during its start-up process, but I can’t see anything to indicate what is making it crash, and as far as I’m aware it is not a known problem, and is not reproducible on our computers. We also know that the affected computer has a mix of software from many repositories (including “unsupported” repositories). We also know that the hardware set-up is quite complex (having HDMI audio via the graphics card in addition to the sound card), so if the problem is hardware related, we are not going to be able to reproduce the problem.
At this point I think I need to ask: How important is it for you to get Audacity working on this machine?
In order to trouble shoot the issue further, I think we are going to need better debug information, but that will require running a “Debug build”, and Ubuntu Xenial does not appear to have a debug build of Audacity.
The way that I would approach this problem (if it was on my machine) would be to build a debug version of Audacity from the source code. This ‘could’ in itself solve the problem, because Audacity would then be built against the libraries that are installed on the machine (libraries on your machine may be from other repositories, so there ‘could’ be compatibility problems with the libraries that Ubuntu used to build Audacity).
Building Audacity from the source code ‘may’ not be straightforward as you may have incompatible dependent libraries installed (which could be the cause of the problem).
IF Audacity (debug) builds OK, and the problem persists, then we would be able to get a “backtrace”, which may at least give us a clue as to where/when the crash occurs.
Pursuing this further is going to take time and effort. We are happy to try and help, but it’s up to you how much time/effort you think it’s worth investing in this (with no guarantee of success). I understand if you decide it’s not worth the effort 
If you do want to continue, do you have any experience building applications from their source code?
There are step-by-step instructions for Ubuntu 14.04 here: https://forum.audacityteam.org/t/building-audacity-2-1-2-on-ubuntu-14-04-lts/40691/1
(Ubuntu 16.04 should be pretty much the same).