What is it about the Lydian Mode that suggests “magic” or “uncanniness”?

Agree with Patrick Alan Burke. I’ll add that the Lydian sounds more strange to Western ears because it not only changes a pitch in the exclusive Major and Minor modes of Common Practice: it changes one of the core pitches of the scale, IV♯, which is disorienting for Western ears.

(It makes me smug that Greek has a IV♭, and Arabic even has a VIII♭. Yes, you read that right.)

Add to that that the IV♯ is a Tritone, the “diabolus in musica”. It is an interval that Western music always found problematic, and the cultural associations have gone along with that.