Robots operating in the real world — quadrupeds on unstructured terrain, manipulators pressing on compliant substrates, multi-robot teams transporting shared payloads — must simultaneously plan complex motions and reason about contact. This dissertation develops a unified planning-and-control framework organized around one technical motif: every problem admits a structure-aware decomposition solved through alternating coordination between subproblems, jointly targeting efficiency, agility, safety, and scalability. Inside the motion layer, three decompositions are developed: a temporal decomposition for contact-rich trajectory optimization of legged locomotion and force-modulated manipulation; a spatial decomposition yielding a distributed MPC for multi-robot collaborative loco-manipulation with team-size-independent replanning; and a system-level decomposition with inertia-aware centroidal / whole-body coupling that generates and tracks momentum-rich agile motions. Across the task–motion interface, a cross-layer decomposition unifies LTL-based reactive synthesis with mixed-integer convex programming for terrain-adaptive locomotion. Together, the four patterns advance contact-rich robot autonomy and provide a methodological lens for future work bridging model-based optimization and learning-based control.