I went about it a bit conservatively, and shortlisted a bunch of names that seemed significant to me somehow or that I liked phonetically, but that didn't feel too...costume ball.
Nadia (which I just liked), Alice (From wonderland, and my favorite Jefferson Airplane song), Rayne (which I also just liked), Lisa (which I choose first, from someone I respected), Sasha (which I currently use-I choose it because I share that name with an obscene british comedian, a silver eyed porn star, and an ice skater, which is utterly perfect, plus the androgynous angle works well for me), and Lyra (because Philip Pullman is amazing).
My middle name was an innocuous "Rodriguez", my mother's maiden name, so I stuck with it. Christine (if that is what you choose), best of luck to you! My advice it this-your love for many people people, the trendiness of your name, and many other factors will change. Choose something that feels timeless, and that you'll enjoy saying thousands of times.