Hybrid hydrogels are hydrogels that exhibit heterogeneity in the network architecture by means of chemical composition and/or microstructure. The different types of interactions, together with structural heterogeneity, which can be created on different length scales, determine the mechanical properties of the final material to a large extent. In this work, the microstructure-mechanical property relationships for a hybrid hydrogel that contains both electrostatic and covalent interactions are investigated. The hybrid hydrogel is composed of a microphase-separated polyelectrolyte complex network (PEC) made of poly(4-styrenesulfonate) and poly(diallyldimethylammonium chloride) within a soft and elastic polyacrylamide hydrogel network. The system exhibits a granular structure, which is attributed to the liquid-liquid phase separation into complex coacervate droplets induced by the polymerization and the subsequent crowding effect of the polyacrylamide chains. The coacervate droplets are further hardened into PEC granules upon desalting the hydrogel. The structure formation is confirmed by a combination of electron microscopic imaging and molecular dynamics simulations. The interpenetration of both networks is shown to enhance the toughness of the resulting hydrogels due to the dissipative behavior of the PEC through the rupture of electrostatic interactions. Upon cyclic loading-unloading, the hydrogels show recovery of up to 80% of their original dissipative behavior in less than 300 s of rest with limited plasticity. The granular architecture and the tough and self-recoverable properties of the designed hybrid networks make them good candidates for applications, such as shape-memory materials, actuators, biological tissue mimics, and elastic substrates for soft sensors.