Magnetoactive elastomers (MAEs) are composite materials consisting of nearly rigid, magnetically susceptible particles embedded in a soft, magnetically insensitive elastomer matrix. These multi-functional materials exhibit field-dependent strains and changes in stiffness. However, the strains that have been achieved experimentally to date are still relatively small (of the order of 1%). The reason for these small strains can be traced back to the dipolar nature of the forces between particles. Large particle concentrations are required to generate strong forces, but large concentrations also lead to large overall stiffness for the composite material, which, in turn, tends to reduce the overall strain. In this paper, we propose a new class of MAEs with doubly layered, herringbone-type microstructures capable of generating much larger field-induced strains of up to 100%. This is accomplished by combining the strong action of magnetic torques on suitably oriented magnetic layers, which interact directly with the applied magnetic field, together with the excitation of soft modes of simple shear deformation in the elastomer layers. Theoretical predictions, based on an exact analytical solution for the macroscopic magnetoelastic response of the materials, allow for the optimization of the microstructure for enhanced magnetostriction.