It looks to me like the Arzela\--Ascoli theorem needs at least some weak form of choice. (I have started an MO question to clarify this.) One often uses this in geometry; for example, to guarantee the existence of minimizing geodesics connecting pairs of points.
Edit: See Andres Caicedo's answer on MO (at above link). The answer is affirmative. Also, the database list of equivalents he mentions contains some very innocuous-looking statements that I bet your friend has never thought twice about using.