I've changed my name as an adult. Yes, I think you are overthinking the "what if people think about-?" parts, but I totally get it. It's hard not to consider every possible angle! But, I absolutely never thought about disorders or dictators and how they sound like
Edie, until you pointed it out! So do not worry too much about that.
I love
Edie.
Eden nn
Edie is really lovely, but I understand that it may feel too religious for you. I see it as more retro myself (I think of
Barbara Eden).
Frida "
Edie" doesn't feel pretentious to me (in fact, it's a little frumpy-cute!). It's similar to
Edie but also, not. I think this would work very well.
To throw another wrench in, what about
Edwina "
Edie"? It's just one extra letter from
Edina, yet it's a whole new name.