We observed the Mars Trojan asteroids (5261) Eureka and (101429) 1998 VF31 and the candidate Mars Trojan 2001 FR127 at 11.2 and 18.1 microns using Michelle on the Gemini North telescope. We derive diameters of 1.28, 0.78, and <0.52 km, respectively, with corresponding geometric visible albedos of 0.39, 0.32, and >0.14. The albedos for Eureka and 1998 VF31 are consistent with the taxonomic classes and compositions (S(I)/angritic and S(VII)/achrondritic, respectively) and implied histories presented in a companion paper by Rivkin et al. Eureka's surface likely has a relatively high thermal inertia, implying a thin regolith that is consistent with predictions and the small size that we derive.