Somewhat relatedly, do you think I should delete my answer? In light of yours I worry that mine is misleading.

Does primeness defined in terms of the commutator agree with the notion of primeness from The shape of congruence lattices? (Maybe this is obvious, my coffee hasn't kicked in yet.)

@JoelDavidHamkins Hang on ... :P

This is great! (I've heard this called a "Welch-style characterization," incidentally, if I'm not misusing the term; @JoelDavidHamkins?)

@HanulJeon Yes, but the trees in this question have height $\kappa$, not height $\omega$.

@HanulJeon Maybe I'm missing something, but can't we phrase an arbitrary $\Sigma^1_1$ statement about $L_\kappa$ in terms of the ill-foundedness of some tree? If so, doesn't that make your upper bound sharp?

@MihaHabič Note that my trees are $2$-branching. Branches through $2^{<\omega}$ trees arrive in $L_{\omega+1}$ by the low basis theorem. If we shift to $\omega^{<\omega}$, then indeed we get trees whose branches arrive arbitrarily late in $L_{\omega_1^{CK}}$ (since otherwise the set of computable ill-founded trees on $\omega$ would be hyperarithmetic), but that's a different setup from my question.

I'll accept this answer once I've had time to read it in detail.

I've fixed to clarify this. Also, part (but not all) of my errors can be explained by me equivocating between two meanings of "compute an isomorphism" - producing the whole isomorphism as a string vs. being able to answer, when given an input element from one structure, what the output element from the other structure should be. I'm used to that equivocation being benign, but of course it isn't here. Sorry, and thanks as always for the answer!