The Armory appears in Lightseeker Camp.
On the bottom of the map, near the bottom right exit, the Armory sits just off the path. Footmen can walk into the Armory instead of following the path. Those that do so disappear inside the building, emerging seconds later having gained new armor and weapons and turned into Paladins. They rejoin the central path instead of the bottom one they joined from.