I've read it on syotetsu https://ncode.syosetu.com/n0715el/95/
From what I gather, "その逸話に違わず" means something like "Different from the anecdotes." Is that correct?
Is this a set phrase or something?
Why is anecdote used here instead of something like rumors or stories?
その[逸話]{いつわ}に[違]{たが}わず
means "Not different from the anecdote" → "Just as the anecdote says" (≂その逸話の[通]{とお}り、～)
[違]{たが}わず is the negative form of [違]{たが}う. The ず is the classical/literary negative auxiliary.
Is this a set phrase or something?
Yes, you'd occasionally see phrases like 「噂に違わず、～」「話に違わず、～」「その名に違わず、～」, which mean almost the same thing as 「噂の通り、～」(just as rumored)「話の通り、～」「その名の通り、～」(as the name suggests)
Why is anecdote used here instead of something like rumors or stories?
You mean why the word 逸話 is used instead of 噂 or 話? It seems like they rephrased the [神話]{しんわ} (myth, legend) in the previous sentence.
