We come to one of my favorite villains, which work fine for a one-shot adventure, but are much better for a slow-burn campaign enemy.
Yuan-ti.
At least, that is the D&D name for snake-men. In the Legends of the Ancient World modules i write, and in Greywater, they are known as Snacas. Snaca is the old English word for snake.
Snake-men have been with us for a long time in fantastic literature. The most prominent example in Sword & Sorcery is found in Howard’s Kull tales, where they are a constant background menace, hinting of improbably ancient, Lovecraftian horror.
They are a race that despises mankind. They were one of the original races when the planet was young, and they have been displaced. Their goal is simple: to take back the Earth (or whatever your planet is named) from the upstart races, usually with humanity as the primary target.
So their long term presence in the megadungeon is straightforward: this is one step in their eventual reclamation of the world. Given the alien way their minds work, it may be difficult for the party to see what their immediate plans are, and how they fit into the generally-known long-term goal. The snacas might even ally with the characters for a while, as some of the party’s actions might go toward the snacas’ long term goal.
As far as the levels they can be found, they will probably be on most levels of the complex. In some areas, just as scouts, while they will be in force at other points in the complex. They will be trying to monitor all events going on, and trying to influence what they can. So there might be a patrol encountered on the first level, observing who is coming into the megadungeon; there might be a checkpoint on the third level, trying to regulate the passage of groups; and there might be a colony on the sixth level, their true base of power in the complex. They might have outposts below this.
The snake-men are adversaries for PCs at every level of experience, and they can be a prominent enemy in the campaign, even as a background nemesis. The snakes might find themselves at odds with other enemies in the campaign, and there is some opportunity for role-playing as the characters find themselves in the midst of strange plots, or try to turn those woven plots to their own advantage.