Maybe using magic involves travelling to and learning to navigate another, even more fantastical place? Such as spirit magic, or dream magic, or travelling to the land of the dead? I think it would be interesting if learning magic also involved getting to know the people of this other domain (such as acquiring a "spirit guide", or making bargains, or learning a language even). Anything from Spirited Away to Hellraiser could serve as an inspiration

There's a cool idea in the Nasuverse called "Conceptual Weapons" - magical weapons that, rather than dealing direct damage, apply certain concepts to people to make them dead. For instance you have the Gae Bolg, a spear that "reverses cause and effect, determining that it has pierced through the heart and warping reality to fit that outcome". So how do you avoid it? Since there's no way to avoid your heart being pierced, you try to ensure that your heart being hit doesn't kill you, one way or another. Or there's the Mystic Eyes of Death Perception, which allow you to see lines on people that you can trace to "apply the concept of death" to them, metaphorically taking their inevitable death in the future and bringing it into the present. A consequence of this is that it doesn't work on immortal beings, since they have no death in the future. (it's actually much more complicated than that, and too convoluted to explain here)

These are kind of OP examples but you get the point - this allows you to approach combat as a puzzle for the players to solve rather than a numbers game.

Jack Vance (namesake of Vancian magic) introduced two interesting concepts in his Dying Earth series. In earlier books magic was essentially invented by the ancient masters who were expert logicians and scientists. Each spell was essentially a proof of concept that a sequence of actions compelled reality to act in a certain way.

By the time of the first short stories in the Dying Earth series, mankind has long since deteriorated due to an overreliance on what is essentially magic to the layperson. Even the wily magicians of the modern time are only capable of rote learning a few arguments at a time; hence the fire and forget Vancian magic system of old D&D.

In later books, magicians have returned to near godly power. They've somehow found a link between djinn-like creatures capable of controlling portions of reality, and the rote rituals of old. They've learned to essentially cut out the middle-man and directly enslave these djinni to do their bidding.