A new technology of magic branch (with animal husbandry, mounted warfare and warg mounted warfare as a prerequisite), that give you the ability to use some magical steeds (like the ones of high level recrutable champs AND different for each race [spider for Reslon, bear for Ironeers, etc..]).
The devs don't even need to create new arts, they are already in the game...