My legal name is Natalie Rose. Obviously, that has to change. I spent forever thinking of names, but none of them really landed with me. So I just decided I'd go from Nat to Matt. It just feels natural with me, and while my given name would make me feel horrible and dysphoric every time I heard it, "Matt" just feels natural. It's not my favorite name or anything, but it's the change I needed (also, I work with a Natalie, so this made things so much easier).
You're lucky to have been born with a gender-neutral name. My whole life, every time I would hear my name or someone would ask my name, I would have a mini panic attack on the inside over it (even when I thought I would be ok living my life as a girl). And going by my middle name wouldn't have been able to help me at all, so I've just been stuck with this curse all my life. As far as the name Alex, I have a roommate with that name. So I always associate it much more as a man's name than a woman's, but I like it for either.
I was planning on legally changing my name soon, but I just had my driver's license renewed, and they changed the license laws in my state. So I won't have a new ID until I'm about 40 (if I weren't changing my name, they would make me use my 21 year old picture until then). So now I'm just gonna wait until I look male enough that my ID will work for me for the next 8+ years. I already hate having to buy alcohol with this ID. Even my bank always comments on how it looks nothing like me already. I guess that gives me time to learn how to write my new name in cursive before I actually get to sign it on things.