This study examines the effect of air-entraining agents (AEAs) type on cement-mortar air content and air-void structure under reduced atmospheric pressure. Six representative AEAs—cetyltrimethylammonium bromide (CTAB), triterpenoid saponin (TS), sodium dodecylbenzenesulfonate (SDBS), sodium abietate (SA), cocamidopropyl betaine (CAB), and fatty alcohol polyoxyethylene ether (AEO-9)—were selected. Their foaming ability and time-dependent foam stability were measured in deionized water and in cement filtrate, and the air content of fresh mortars and the distribution of air-voids in hardened mortars were determined at 100 and 60 kPa. The results show that, at 100 kPa, TS, CAB, and CTAB produced higher initial foam height and better foam stability in deionized water than AEO-9, SA, and SDBS. TS and CAB also maintained a higher number density of bubbles and slower coalescence. In addition, all surfactant systems showed lower initial foam height and stability in cement filtrate than in deionized water, with SDBS, SA, and AEO-9 experiencing the greatest declines. When the pressure decreased from 100 kPa to 60 kPa, the mortar air content dropped by 8–15%, with the smallest reduction for TS (~8%) and the largest for CTAB (~15%). At 60 kPa, air voids with radius < 250 μm decreased markedly in hardened mortars: by 51%, 25%, and 28% for the control, CTAB, and AEO-9 mortars, respectively; but only by 14% for TS, highlighting its superior retention of fine air voids. Overall, amphoteric/saponin-type systems (represented by TS) exhibit better tolerance and stabilization, and are recommended for high-altitude concrete.