From what I've seen of Toady's work, and what I've heard from his posts and podcasts, I want the same kind of magic that he does: Magic based not on fantasy tropes, but on the legends and fables that fantasy is based on. He does not see goblins as the D&D cannon fodder - he sees them as inherently evil baddies that come in, mess things up, steal your children, and are otherwise organized boogeymen. They are the Goblins of yore.
This brand of magic, this ... relative perspective of reality, is exactly what is so difficult to pin down in a fantasy game. In a game, it's difficult to get beyond the idea of magic as a tool to destroy your enemies - after all, most games are about destroying enemies, or about achieving specific goals. I don't even necessarily want to see magic work in a way that easily benefits my fortress. I want to see it work for itself, not for me - or for my Dwarves.
I want to see magic as... strange. Unpredictable. Unknown. I want physics-breaking things to happen and still find them difficult to explain. The magic of True Names, of places that are there but aren't, or only there at certain times. The magic of stars and twilight, of shadows and the sun.
I don't want to see fireballs and magic missiles, or consecrate, or any of that carp. Magic is a force of nature. It is not controlled by anyone, nor does it allow the control of nature. It's a very difficult concept to nail down, and all the more so because we're already dealing with a game about Dwarves, including Elves, Goblins, and Demons, and Fire Men. Even if we can come up with a kind of magic that we can all agree on (which we won't), finding one that also makes a worthwhile addition to a game is a difficult task.
I want magic to simply exist. If someone shows up at my fortress that can work a little bit of magic, fine. But being a magician does not at all make him a military one. Perhaps he's an oracle. Perhaps he's more like the pied piper, and lures all my Dwarves away with the charming sound of a bagpipe, then ransomes my nobles for their return. Perhaps he summons demons - and not to help me.
So... I'm not sure. Again, it's a very difficult question. I want the magic to work in a way that I can interact with it in the game, but not in a way that I will always interact with it in the same way, or in a way that necessitates that interaction. I want magic to be about destiny, about dark forces, about charms and enchantment. I want it to leave me with a sense of wonder, not with a sense of quantifiable bonuses and a field of dead enemies.
Magic is not a tool. It is the unexplained, the mystic, the crazy. Magic is the stuff of dreams and nightmares.
Or at least... that's how I see it in DF. I can see Dwarves using, perhaps, the magic of runes and stones, but I'm not sure how that would translate to a valuable gaming experience in Dwarf Fortress without the question of why this magic isn't used everywhere, and why on earth anyone would opt out of it.