Whatever you do, don't listen to Psy.

I'd pick something you have a keen interest in, but not too mainstream. Take a favourite book character, for example, since those sorts of names aren't overused. Just try and stay away from FF, or you'll be unrecognisable amongst the sea of Yunas, Clouds and Sephiroths.