I managed to do a build with the other, more optimized build option now. It worked perfectly in my VM and Ubuntu 18.04.03, but on my USB stick version, it still had issues, although I'm not sure if I just configured Ubuntu wrong or if the game code is to blame. Unfortunately, I don't know many other Ubuntu users I could ask, so...could you help testing it? You can find the build here, the password is "chiphop".
https://fricochet.itch.io/chiphop-beta
There are two versions. In theory, the YYC one should be better optimized, but may require additional packages. The VM one probably has worse performance, but may be more compatible. Although on my VM, there was no real difference.
(Well, in this case, the VM version also has an additional feature and an "L" button on the right, which wasn't added to the YYC build yet, but that would be added for a future public release as well. Should hopefully not influence whether they run smoothly.)