Physical walking is often considered the gold standard for VR travel whenever feasible. However, limited free-space walking areas in the real-world do not allow exploring larger-scale virtual environments by actual walking. Therefore, users often require handheld controllers for navigation, which can reduce believability, interfere with simultaneous interaction tasks, and exacerbate adverse effects such as motion sickness and disorientation. To investigate alternative locomotion options, we compared handheld Controller (thumbstick-based) and physical walking versus a seated (HeadJoystick) and standing/stepping (NaviBoard) leaning-based locomotion interface, where seated/standing users travel by moving their head toward the target direction. Rotations were always physically performed. To compare these interfaces, we designed a novel simultaneous locomotion and object interaction task, where users needed to keep touching the center of upward moving target balloons with their virtual lightsaber, while simultaneously staying inside a horizontally moving enclosure. Walking resulted in the best locomotion, interaction, and combined performances while the controller performed worst. Leaning-based interfaces improved user experience and performance compared to Controller, especially when standing/stepping using NaviBoard, but did not reach walking performance. That is, leaning-based interfaces HeadJoystick (sitting) and NaviBoard (standing) that provided additional physical self-motion cues compared to controller improved enjoyment, preference, spatial presence, vection intensity, motion sickness, as well as performance for locomotion, object interaction, and combined locomotion and object interaction. Our results also showed that less embodied interfaces (and in particular the controller) caused a more pronounced performance deterioration when increasing locomotion speed. Moreover, observed differences between our interfaces were not affected by repeated interface usage.