Eh, does it matter if they're gay? As long a they're suitably heroic then no one should mind playing them. There are lots of ways you can play it where that would be a good puzzle answer. I guess why do you assume anyone who does not have a sexual preference be straight? I mean, considering how overcompensating Duke Nukem is, I could see him being in the closet.