I'm partial to the suggestion that PHALANX agents start out at random spawns throughout facilities they would be expected to frequent (Command, Quarters, Storage, etc.), but then have a limited number of turns to move into position before the aliens breach the base.
The alien breach could be handled in several ways, though I don't think teleportation is reasonable at the moment. Explosives make for a better explanation in my book. Entrance obstructions could be placed on the maps, which are then demolished at the start of Alien turn X, allowing the invaders to enter. The obstructions could also be alien-destroyable, if more randomization is preferable. Alternatively, using the alien reinforcement concept that I have heard discussed around here before, the initial alien invaders may not even have to be on the map right away, and additional aliens could be introduced at the start points as the invasion progresses.