This is quite hard to answer. Games like Bioshock Infinite I really don't mind the character being male because the story was so very good, plus it was necessary for the storyline.
However if a game like Skyrim did not allow gender choice than it would annoy me to no end.
I think maybe there is a difference between immersing yourself in the character (Skyrim) and immersing yourself in the Story (Bioshock).