Yes, Apple’s archive utility, as I’ve seen myself, gives you the unwanted folder. However, if I understand you (again, per my experience), functionality is okay and it is with the third-party tool that things break.
I’m guessing (and I think it’s a good guess) that the other tool is stripping the necessary permissions from the Linux .exe, and perhaps also from the .so files in the Libraries folder. This can be fixed in the Linux terminal with some chmod commands.
I do my zipping on the target platforms. In the case of Windows, that’s where I do my code-signing and installer-building anyway, prior to compressing. I’m using Fusion VMs, so dragging the uncompressed build folders into the VM is easy.