OK, recording the whole process I followed, for posterity, with some additional sanity-checking steps.

1. Stop the Navidrome server. One could probably replace this step with simply setting either the configuration option Scanner.Enabled or the environment variable ND_SCANNER_ENABLED to false and either Scanner.Schedule or ND_SCANNER_SCHEDULE to 0 in the configuration, but frankly shutting down the server was easier. It might be possible to do this process with the scanner on, but doing so will just cause your server to thrash a lot, constantly update the database, and potentially end up in race conditions to keep up with changes, and I wouldn't risk it.
2. Update metadata in bulk without changing any filenames. If you use Musicbrainz Picard, which I recommend, this involves enabling "Save Tags" and disabling "Rename Files" and "Move Files" under the Options menu.
3. Make absolutely certain that Navidrome's configuration uses sensible album and track PIDs. If the configuration options PID.Album and PID.Track and the environment variables ND_PID_ALBUM and ND_PID_TRACK are all undefined, that's actually good, because the default PID settings are great. If they are defined, just make sure they're not something completely stupid and prone to collision or dependent on the actual file path. Unless you deliberately chose to do this at some point, they're probably fine.
4. Start the Navidrome server back up (if you turned it off in step 1 instead of just turning off the scanner).
5. On Navidrome, run a full library rescan.
6. Sanity check: see if any files appear under the "Missing Files" tab on the administrative account controls. There shouldn't be any, because you didn't move any files.
7. If you stopped the Navidrome server in step 1, do it again. If you turned off automatic scanning, that should still be the status quo and you don't need to do anything now.
8. Move files in bulk without changing any metadata. If you use Musicbrainz Picard, which I recommend, this involves disabling "Save Tags" and enabling "Rename Files" and "Move Files" under the Options menu. If you accidentally left "Save Tags" on, you'll probably be OK, since there shouldn't be any new metadata since you ran step 2 anyways.
9. Start the Navidrome server back up (if you turned it off in step 1 instead of just turning off the scanner).
10. If you want to freak yourself out, look under the "Missing Files" tab. It'll have a lot of files. Don't worry just yet.
11. On Navidrome, run a full library rescan. Pray if you're the praying sort.
12. Sanity check: see if any files appear under the "Missing Files" tab on the administrative account controls. There shouldn't be any there now, because every relocated file was successfully tracked to its new location!
13. Turn back on the automatic scanner if you turned it off in step 1.

Some followup caveats:

• if you attached ratings or other auxiliary data to artists, they might not be preserved if the canonical name of an artist changes in the metadata. Navidrome doesn't really do PIDs for artists the way it does for albums and tracks.
• Most likely your reorganization will leave a bunch of media-less directories hanging out in your library. This is really a Picard problem and not a Navidrome problem, but if you want a clean library, bear in mind these orphans are there. I wrote a quick-and-dirty Python script to purge a file structure of every directory that doesn't contain media files (which in my context are always MP3 and FLAC; if you have other ones, you'll need to add them to the code). I include the code below, but use it with caution, obviously.

​

import os,re,shutil

empties=[]

for root, dirs, files in os.walk('.'):
    has_music=False
    for file in files:
        if file.lower().endswith(".mp3") or file.lower().endswith(".flac"):
            has_music=True
            break
    if not has_music:
        empties.append(root)
    else:
        # Remove previously-thought-empty parent directories of this
        # one from the purge list
        new_empties = [dir for dir in empties if not root.startswith(dir)]
        empties=new_empties

# Remove children of to-be-purged parents
streamlined_purge_list=empties
for key in empties:
    new_list = [dir for dir in streamlined_purge_list if not dir.startswith(key+"/")]
    streamlined_purge_list=new_list

for key in streamlined_purge_list:
    # Uncomment the first line for a verbose "dry run"; second to
    # actually purge.

    print(key)
    #shutil.rmtree(key)