How do I run a script before everything else on shutdown with systemd?

I got it!

Take solution Long running process with StopExec and modify it like so:

autobackup.service:

[Unit]
Description=Slow backup script
RequiresMountsFor=/mnt/BACKUP /home

[Service]
ExecStop=/etc/systemd/system/do_backup.sh
Type=oneshot
RemainAfterExit=yes

[Install]
WantedBy=multi-user.target

Note the line:

RequiresMountsFor=/mnt/BACKUP /home

It works as expected this way.

No need to create or edit service files. Simply drop your script in

/usr/lib/systemd/system-shutdown/

https://www.freedesktop.org/software/systemd/man/systemd-halt.service.html

Immediately before executing the actual system halt/poweroff/reboot/kexec systemd-shutdown will run all executables in /usr/lib/systemd/system-shutdown/ and pass one arguments to them: either "halt", "poweroff", "reboot" or "kexec", depending on the chosen action. All executables in this directory are executed in parallel, and execution of the action is not continued before all executables finished.

I use it to simply beep the PC speaker.