Nature provides exceptional examples of the mobility and dexterity capabilities of animals. From cheetahs running at top speeds of 130 kph to giant squids with over five-meter tentacles hunting at extreme ocean depths, evolution and time have enabled animals to navigate their habitats through an almost effortless interplay with the surrounding environment. It is that, for animals, the ability to move through the world is intrinsic to the design of their bodies and brains, which have evolved in unison to achieve energy efficiency and robustness to unexpected events. The role of the passive dynamics of the body in biological locomotion is envisioned as a form of embodied intelligence triggered by physical interaction with the world. This dissertation aims to contribute toward the design of legged robots embodied with mechanical intelligence via the concurrent design (co-design) of their mechanical and control systems. The challenge for the design of legged robots is on achieving a synergy between body (hardware) and brain (control) as observed in animals. This challenge is accentuated by the lack of computational co-design tools, and the complexity of jointly modelling dynamics, hardware, and control systems. Traditionally, tasks of mechanical and control design are executed separately, with the controller primarily responsible for forcing behaviors through non compliant morphologies. Moreover, often to alleviate the computational complexity, the consideration of isolated scenarios (i.e., tasks and environments) at design time ignores the uncertainty that legged robots need to face to operate in the real world. This dissertation proposes a co-design framework rooted in trajectory optimization (TO) that produces robots while considering uncertainty at design time.The contributions of this dissertation are reflected along three main axes, increasing versatility, improving energy efficiency, and adding robustness reasoning to a design, all made possible via algorithms that address computational scalability. To ensure versatility, the presented framework models scenarios that a robot could face using probability measures for the description of potential tasks and environments. These probability measures are accounted for in the design formulation through the use of Stochastic Programming (SP) constructs. Combining SP with TO ensures that a design excels in a range of scenarios, with the controller enabling adaptability and the morphology promoting energy efficiency. In that sense, mechanical intelligence arises from the morphology relieving the control effort when the natural dynamics of the robot contribute productively to accomplishing a task. The benefits of co-design are shown on monopod and quadruped robots that exhibit fast and robust performance completing a locomotion task (e.g., jumping), while reducing the energy use from their actuators. Robustness is assessed from the perspective of a robot withstanding disturbances while still showcasing fast performance and energy efficiency. To achieve robustness, this dissertation is aligned with efforts in the robotics community developing feedback controllers for motion planning. The proposed co-design framework is the first to consider the co-optimization of the morphology, a nominal trajectory, and a feedback control policy for disturbance rejection. The co-optimization of the morphology, the nominal trajectory, and the feedback control policy achieved improved results in terms of tracking performance, robustness, and energy efficiency compared to state-of-the-art single-scenario co-design implementations. The price to pay, even with open-loop control strategies, is a challenge to computational scalability, particularly with respect to the number of scenarios. To address this challenge, this dissertation proposes parallelizable algorithms for large-scale co-design problems (i.e., including 30 scenarios) using the Alternating Direction Method of Multipliers (ADMM). The scalability gained through the ADMM supported the engineering of mechanical intelligence in a quadruped robot equipped with pneumatic cylinders as parallel elastic actuators (PEAs). Compared to the case without PEAs, the design with added compliance reduced its cost of transport (CoT) by 61% and required less time to cover larger jump distances. To support the optimization findings, experimental results with the MIT Mini Cheetah validated the co-design principles in this dissertation, demonstrating the engineering of mechanical intelligence via the reduction of the CoT (up to 19%) with the robot executing trotting gaits and using a standard controller not co-optimized for exploiting passive dynamics.