How do spells decide which intro to play?

Have you looked at bank C3 at all? That's where all the menu code is. There is an excellent disassembly from Novalia Spirit available on RHDN. I'd recommend searching banks C1 and C3 for references to $1D54, and then focus on instances that follow with AND #$07. That's where the menu setting for the magic order is stored in RAM.

There's a table at C3/4F49 that you will need to change. There is also code at C3/2C14 and C3/514D that will need to be modified with your new spell indices.

I'm surprised your changes to spell sorting didn't work in the battle menu. It looks like you've changed the right thing. I'm also surprised that Quick doesn't work. I don't see anything else to change other than what you've already done.

Maybe the C3 file I found is out of date.  I looked up "Novalia Spirit" on RHDN and downloaded the collection, which had a BUNCH of files in it (as opposed to the one file for C3 I had before), so I'm guessing that was the case.

I've mostly been searching for comments, instead of specific bits of code.  I'll look through this new C3 repository I just downloaded and see if I can figure out what I'm missing.

Yeah, the code changes I made in the previous post didn't impact battle sorting at all.  I wonder if it's just for Gogo, or if the menu settings are overriding them.
Thanks for the heads up on where to look; I'll edit this post if I figure out what I'm doing wrong.

EDIT: Ooh, this is promising... I bet this is the culprit.  Thanks for the address, I'm going to fiddle with this for a while.

Code:

Starting spell for each Magic type, sorted based on Mag.Order
C3/4F49:    2D 00 18 FF    ; 1: Cure, Fire, Scan  [24 00 12?]
C3/4F4D:    2D 18 00 FF    ; 2: Cure, Scan, Fire
C3/4F51:    00 18 2D FF    ; 3: Fire, Scan, Cure
C3/4F55:    00 2D 18 FF    ; 4: Fire, Cure, Scan
C3/4F59:    18 2D 00 FF    ; 5: Scan, Cure, Fire
C3/4F5D:    18 00 2D FF    ; 6: Scan, Fire, Cure

EDIT!: Yay!  This and the block that comes after it fixes the sorting, both in menu and in battle.  Strange that the one in with battle commands doesn't seem to contribute.

Still need to sort out menu casting issues, Quick, and now Imp (I just tried, and even though it's not grayed out, it won't cast when in the wrong slot...).  Going to see what I can find in these new documents.
EDIT: AHA! Imp was hiding another hard-coded call in the battle loop.  Sneaky.  C2/3217.  All that's left is fixing Quick... Scratch that, I'm a goof.  My spell test file didn't have the property set.
You solved all the problems, Everything.  You rule!