I'd look to the "Battlestar Galactica" board game for some inspiration.
I'd probably keep the idea that the group is being infiltrated a secret. I may introduce the idea that other organizations have been infiltrated, but not the PC group. I might, like the BSG BG, hand out cards at the beginning and middle of the game that have mundane info on them except the "You are a Skrull" card (the only real card that matters). These cards would actually be disguised "loyalty" cards, like in the BSG BG.
You'd need to have at least 2 cards per player to have enough cards for both the beginning and middle of the game. This way, if there is only 1 Skrull card, there may not be a Skrull at the beginning of the game; and if players start to suspect at the beginning that a PC could be a Skrull (but there really aren't yet); that's when the paranoid-fun really starts to kick in.
Also, at the beginning, a player may not be a Skrull and actively hunt out Skrulls; only to find out that he/sher is a Skrull later in the game. So, BSG BG players will recognize that you may not want to play too well in the beginning because if you end up being a Skrull in the end, it would be just that much harder to undo what you've done. But, this is turning the game much game-ier; not very Super-heroic.