There has been a considerable interest in developing stiff, strong, tough, and highly stretchable hydrogels in various fields of science and technology including biomedical and sensing applications. However, simultaneous optimization of stiffness, strength, toughness, and extensibility is a challenge for any material, and hydrogels are well-known to be mechanically weak materials. Here, we demonstrate that poly(ethylene oxide)-based dual stimuli-responsive semicrystalline poly(urethane–urea) (PU) copolymers with high hard segment contents (30 and 40%) can be utilized as stiff, strong, tough, and highly stretchable hydrogels with an elastic modulus (4–10 MPa) tens to hundreds of times higher than that of conventional hydrogels (0.01–0.1 MPa), strength (7–13 MPa) and toughness (53–74 MJ·m–3) fairly comparable to those of the toughest hydrogels reported in the literature, and stretchability beyond 10 times their initial length (1000–1250%). In addition, the shape-memory program has been used to tune the room temperature stiffness and strength of the studied PU copolymers. Finally, the materials show fast shape recovery (less than 10 s) during both heat- and water-activated shape memory cycles, which can be adjusted by a simple modulation of the hard segment content and/or soft segment molecular weight. Our findings may be of interest in emerging biomedical and sensing applications.