I tend to wait to really launch into teaching magic until after I have Seraphim, because more than anything else, I want everyone to have basic medical abilities. Carbuncle is nice too, for various utility-based stuff...

Have you ever tried keeping a character magic-free for the Coliseum? It's always nice when one more attack will win the fight and your character casts Teleport.