If you want people using non-Debian GNU/Linux to use your cli, you’ll need a different way to install it. This may seem a hassle, but it is common. Linuxbrew, for instance, asks you to have ruby installed, and run a non-trivial command - in the sense that it’s not easy to remember the full command, unless you install it frequently.
What you could do, then, is use the #!/usr/bin/env julia approach, and ask the user to put it somewhere “visible”. In my case - JuliaBG - I asked the user to chmod and cp to /usr/local/bin. If you still think this is too much for the user, create a Makefile that does it automatically, and ask the user to sudo make install.