I have by chance, been studying the secular evolution of "magic" in several different cultures throughout human history. It dovetails quite nicely with my interest in scientific and technological history, because all science started as magic e.g. astrology --> astronomy, alchemy --> chemistry.
Short Answer:
Magic feels like magic, when its effects are created by communication with personalities that can arbitrarily alter material reality in some fashion. Magic feels like another form of physics, when no personalities are involved. Characters should have to learn specific words, rituals etc to evoke personalities and should often have to bargain with them.
In your story, I think it would best to introduce magic first as apparent anomalies in materialistic measurements, something that could be explained with more materialistic knowledge and then gradually make the characters aware that magical personalities of some kind can manifest material effects, based on their the will or whim of non-material personalities.
The effects on working science might be fairly minimal if magic is rare. Scientist would just define magic as a "special case" and go on. The social and political implications could be huge, however. Our political institutions and most of social assumptions in the modern West rely directly on the clockwork model of reality built by Descartes, Newton and other early scientist. If reality suddenly becomes arbitrary, even little pockets of it, a lot political, legal and social processes could breakdown.
E.g. In a criminal criminal investigation, the investigators would first have to element a magical cause, i.e. the murder victim was killed by the Fey Wild hunt, or because they evoked the wrong magical personality and pissed it off etc all before they get around to the the abusive spouse.
Engineers and programs might actually have to check for gremlins or build gremlin resistant systems. Police and military might have to adapt to fighting magical creatures or effects.
We'd also start burning witches again, this time for valid reason. The ability to alter other people's minds, torment, injure or kill remotely with no obvious link between the attacker and victim, is utterly horrifying. Moreover, as long as the "witch" was alive, could anyone ever be certain they weren't casting spells from prison? Likely, witchcraft would become a capital crime.
Long Answer
Background
It's important to not that prior to the 16th century at the earliest, no culture made a hard distinction between a materialistic "natural" world, the supernatural or the cosmology of the local religion. They were all part of the same set of phenomena and blended together seamlessly. Newton for example, spent a lot of time working on alchemy seeking what we would consider non-material magical results. Likewise, he saw the cosmology of his Christian faith as the basis for his "clockwork" cosmology.
The key defining attribute that separates a magical world view and a materialistic scientific world view is the concept that the non-human and non-living world contains cognition, memory, desire, language and personality.
In other words, in a magical world, you alter that world by communicating with some non-material being which in turn can influence the material world.
In a materialistic world view, only living organism can be communicated with. Non-living objects, like rocks, are manipulated by apply various material effects to them e.g. heating, cooling, acids, smashing etc.
In Western magic you have to periods or groups: the Pagan era which overlaps and was eventually subsumed by Abrahamic magic which is magic associated with the world models of Judaism, Christianity, Gnosticism and Islam all the religions that trace back to Abraham. The major pre-Abrahamic influences come Egypt and Summaria
The major differences between the Pagan and Abrahamic magics lays in the immediacy of personality they communicate with. In Pagan magic, one evokes a specific non-material personality, which usually has specifically defined powers and regional range. Usually, dealing with the supernatural personality is pretty much like bargaining or trading with a powerful human being. Just as there are rituals for an audience with a king or priest, their are rituals for getting an audience with the entity. Just as humans won't do much for free, neither will the entities.
In Abrahamic magic, the cosmos, materialistic and otherwise, is created and manipulated by specific words e.g. which came originally from the words spoken by the creator God. "And god said, 'let there be light.'" Probably the best analogy would be that we all exist in a computer generated virtually reality, ala "The Matrix" and a magician is someone who knows the words to rewrite the program on the fly.
Note that in Abrahamic word magic, speaking, writing or sometimes even thinking of the word/sign/sigil, triggers their effects because the "word" and its effect are one and the same thing. Therefore, the real words an symbols must be encoded somehow so that people can learn them, without activating accidentally activating them.
Interestingly, specific personalities were reintroduced to the Abrhamic magical system by making specific angels and demons either the manifestations of or care takers for specific words or concepts of creation. The apocrypha of all the Abrahamic religions are full of complex hierarchies and relationships for these beings. Some historians classify the cults of Saints in Catholicism, each the patron saint of some activity or event, as form of personality based magic.
Modern Concepts
What most people think of as "magic" in modern West, even Wiccan and the like, is actually Abrahamic magic were the magic words themselves can create a direct effect. As well, in many stories, magic is actual a form of physics, devoid of personalities, were the mage tosses around "energy" in some form. I think we tend to shy away from true traditions of magic of any form because they are inherently linked to specific religious cosmologies.
Strongly Differentiating Magic from Materialism in a Contemporary Fantasy
1) Don't evoke any concepts even vaguely materialistic e.g. energy.
2) Magic should violate fundamental scientific laws such Conservation of Energy, Conservation of Momentum or violations of Newton's laws of motions.
... most importantly...
3) There should be somewhere in the magic a definite personality of some kind. It can be a distant creator god who leaves knowledge of the words of creation behind attached or not to other beings, or it can be specific non-material personalities strongly attached to place or concept.
In any case, magic is about speech and/or communication and nothing else. Again, the concept of programing a virtually reality program from within the program is a good analogy. The magician doesn't have to worry about energy or conservation or anything else. He alters reality by effectively rewriting the rules of reality on the fly using either the words that created reality in the first place or by evoking a being who knows how to do the same.
For example, a magician would set something on fire by either 1) summoning a personality that can arbitrarily create fire or by 2) creating a spell/program that alters the properties of the target such that it burst into flames.
All science is based on the Great Assumption i.e. everything that exist is subject to materialistic measurement and everything follows specific rules, even if we don't always know what those rules are. Scientific models are judge by their ability to predict the future evolution of the modeled system.
All you have to do to throw a monkey wrench into scientific method is arbitrarily alter some aspect of the material universe by means that cannot be measured and which follow no rules other than the whims of the magician or supernatural entities.
For example: Turning a human being into a sentient frog capable of speech, simply cannot be done under materialistic rules even if you evoke bizarre levels of quantum probability. The extra mass has to go somewhere, the movement and reconfiguring of tissue from human to frog would have to generate heat and you can't cram a human brain into a frogs neurology. If performed repeatedly and at will, that would make quantum fluctuations so incredibly improbable that a non-materialist effect would be more plausible than unknown materialistic effects.
But you still need the Second Law of Thermodynamics
The story paradox created by magic boils down to one of limitations. To have story, one must have conflict and struggle and that means that any magical elements must come with some kind limitation, usually attached to the material world, that limits what magic can do. Otherwise, magic either immediately resolves the problem or someone sneezes in the middle of a spell and causes the universe to implode.
All our human perceptions of reality and story are ground in the 2nd law. Our intuitive model of realty says we can't get something for nothing, and that includes magic. Magic CANNOT use pseudo-physics like "mystic energy" but it must have a cost in time, knowledge, trade or consequence.
Ideally, the cost should be utterly unrelated from the effect sought e.g. the cost of having a supernatural personality fix a flat tire would be to have the mage perform the "naked chicken dance" in public. The only linkage between the dance and fixing the tire is the entity who thinks it's funny to humiliate you.
Well, you get the idea.
