I am currently turning one of my unfinished book into a choice of games thingy, and I have to deal with exactly this. Since it was a book, all the characters were of course a certain gender in my head, and now I have to sit down and rewrite everything.
Still, for me it is a really worthwhile exercise, because I am finding that looking at the story from a different point of view actually is a lot of fun.
That being said, it is still exactly the same MC as in the book. I have changed nothing about the background, because that is an integral thing to the plot. I just lowered the bar for identification.
Another thing I realized was that it felt more natural to just insert the choices as you go along, at the first point they become divergent. For example, the Rooster nickname works just as well for both men and women I feel, and it is only when someone calls Clyde by name that you would need a simple set name thingy. Same when the issue of gender first pops up.
I am quite new at this as well, but I seem to get the feeling here that a lot of people are enjoying reading/playing a story without having to do the inevitable gender/race/sex AU in their head that you have to do for most modern media if you want to identify with someone outside the norm.
That being said, it can snowball fast, so make sure you pick what really matters.
As for being less iconic. I think Shepherd and Hawke for example (from dragon age and mass effect) managed to be quite iconic despite the gender options. After all, what makes someone iconic is not how they look, it is what they DO.