Hexapod robots are six-legged robotic systems, which have been widely investigated in the literature for various applications including exploration, rescue, and surveillance. Designing hexapod robots requires to carefully considering a number of different aspects. One of the aspects that require careful design attention is the planning of leg trajectories. In particular, given the high demand for fast motion and high-energy autonomy it is important to identify proper leg operation paths that can minimize energy consumption while maximizing the velocity of the movements. In this frame, this paper presents a preliminary study on the application of a hybrid multi-objective optimization approach for the computer-aided optimal design of a legged robot. To assess the methodology, a kinematic and dynamic model of a leg of a hexapod robot is proposed as referring to the main design parameters of a leg. Optimal criteria have been identified for minimizing the energy consumption and efficiency as well as maximizing the walking speed and the size of obstacles that a leg can overtake. We evaluate the performance of the hybrid multi-objective evolutionary approach to explore the design space and provide a designer with an optimal setting of the parameters. Our simulations demonstrate the effectiveness of the hybrid approach by obtaining improved Pareto sets of trade-off solutions as compared with a standard evolutionary algorithm. Computational costs show an acceptable increase for an off-line path planner.