Okay I think I finally figured this out and want to add it in case anyone runs into this issue. It's been awhile since I was working on the game regularly (though hopefully that'll change now) so apologies when my terminology is off.
The big difference between the examples I was following and my own setup was that the examples were all single-level games, and mine has multiple levels, but is run from this global node that handles level loading/transitions, stuff like that. (In effect, each level of my game is a standalone game because I have no idea what I'm doing. Originally it'd been just one level, but I eventually made copies of level one, redid the layout etc, and changed the old main files into level1, level2, etc. Then I used global nodes to handle switching between levels, saving, stuff like that.)
But I'd originally declared the StateMachine class in a script inside level 1. So when I ran the game from this outer level, I think it didn't see the class declaration until I actually opened Level 1 in the editor and opened the relevant .gd file.
To fix this, I created a State.gd and a StateMachine.gd file to declare the classes and moved them up to the root. Then I adapted the individual instances in the levels to extend State and StateMachine. Now it's working reliably from a cold start.
This was one of those problems that's probably pretty easy to show someone, but hard to ask about, and I wish my terminology was more helpful here, but if you run into weird class issues, and your game has a weird layout like mine, maybe that's the issue.
Now I'm gonna go make some NPCs.