Note: The word magic(k) has been used in so many different spellings under so many different names, most likely due to its roots in fiction and the supernatural, that any spelling is certainly valid for something as informal as an internet forum.
Anyhow, I think that some sort of shamanistic ritual would be great for improving some of the innate things that don't really improve otherwise, like patience, willpower, memory, etc. Pretty much you go to a small, randomly generated fantasy plane with cryptic instructions like "Follow the path of fading life" or "tread on the coals" where you follow a blood trail/burnt area to an eventual goal. If you "die" during the dream you can come out of the experience with reduced attributes or simply have to try again. Perhaps if the RNG is really mean during worldgen you'll occasionally be stalked by the spirit creatures hungry for the soul that was denied to them...
Another thing I'm really excited for is the "apprentice/master" relationship Zach had in once of his recent stories. The primary thing here is that it's hard to establish a relationship with someone right now. I don't think we could ever have joint quests with AI (just look at how badly it works in other games. The words "escort quest" make any RPGer shudder) but I think that having a mentor send you out to collect books, perform research (which will also factor into randomly generated planes of existance and the powers contained therein, something useful to know with other adventurers) and perhaps calm down (read: slaughter) a fearful mob of peasants that are distrustful of the unknown powers you meddle with. Perhaps if wizards are associated with a village you could either help the villagers in their battles or punish your slaves for not working faster or something. Think "YOU ARE WIZARD!" with less abject silliness. Or the same amount knowing Dwarf Fortress. Court wizards could also be incredibly interesting, especially if some of them are evil and influencing their kingdom; you could then change the whole world by killing off this wizard and changing a warlike kingdom into a completely different place.
TLDR: I'm really excited for the possibilities magic(k) will bring into the game. Maybe too excited. I could write ideas for pages, but I'll control myself and wait a bit to see what others think.