Exposure to small public urban green spaces (SPUGS) has been demonstrated to have mental benefits for older adults. However, studies on identifying the objective environmental features of SPUGS and their effects on mental restoration for older adults remain limited. This study employed a multilevel regression model to investigate the restorative and vitalizing effects of the environmental features of 11 SPUGS in Tokyo. Onsite measurements were conducted in Kita-Ku, and 202 older adults were surveyed. The results showed that: (1) The fitting curve of the green view index and Restoration Outcome Scale (ROS) score showed an inverted U shape—both green view index and boundary enclosure had a strong impact on the mental restoration of older adults; (2) The colorfulness index showed the strongest relationship with the vitalizing effect. (3) The sky view factor and number of seats only influenced the ROS score, while the results of revitalization suggest that large areas of water should be avoided. (4) Physiological Equivalent Temperature (PET) was also confirmed to have negative effects on the mental restoration of older adults in autumn. These empirical findings can be used as a resource to promote the mental health of older adults in the design of SPUGS in high-density Asian countries.