I always imagined that fighting your first Yuuzhan Vong should be like the first time you fight a Skaarj in Unreal.
After you have completed an objective, the door in front of you closes, one by one all lights go out as you frantically run back but the door at this end of the corridor closed, too. As you stand alone in the dark corridor you light your lightsaber to be able to see bit and all of the sudden it's MOTHER****ING YUUZHAN VONG IN A MOTHER****ING CORRIDOR!!!!
But IMHO an introduction to the Yuuzhan Vong could work quite well in a FPS. In the first few levels you could be fighting stormies, just like in the old days and later in the game you could actually fight together with the stormies the common enemy, the YV, thus combining familiar elements with something new.
Sorry for the lousy German