I ended up taking the boring route: I went with the name that my parents would have named me if I’d been AMAB. My deadname didn’t have a masculine version, and there were no other names starting with the same letter I liked, but then I remembered when I was about 11 I’d asked my parents what they would have called me if I was born a boy. So I tried out that name, and found that it just seemed to fit. It’s not too common, I don’t know anybody else in my personal life with the same name, but it’s common enough that people know how to spell it, and it fits my age.
I didn’t like the middle name that my parents chose, though. It made my whole name a bit of a mouthful, especially as I had a longer surname at the time as well. Since middle names aren’t something that get used often, I went a bit more exotic with it, and picked the closest real-world version of my favourite OC’s name.
My spouse and I changed both of our surnames at the same time, as I had taken his surname when we married, but neither of us had a strong emotional attachment to it. So we selected a new one. We’re both descended from a white minority group that has its own ancestral language, so we formed our new surname to fit in with the cultural naming style of that language. As a result, our surname is unique, yet doesn’t look out of place in a phonebook.