Piezoelectric matrix-inclusion composites based on lead-free ceramics have attracted attention due to the possibility of manufacturing environmentally friendly devices using scalable emerging technologies such as 3D printing. However, lead-free materials lag lead-based piezo-composites in terms of performance, thus necessitating new design strategies to escalate piezoelectric response. Here, we build a modeling paradigm for improving the piezoelectric performance through improved matrices and optimal polycrystallinity in the piezoelectric inclusions. By incorporating carbon nanotubes in the matrix, we demonstrate 2-3 orders of improvement in the piezoelectric response, through simultaneous hardening of the matrix and improvement in its permittivity. By tuning the polycrystallinity of the piezoelectric inclusions, we show considerable improvements exceeding 50% in the piezo-response, compared to single crystal inclusions. We further analyze the influence of carbon nanotube agglomerations at supramolecular length scales, as well as vacancy defects in the nanotubes at the atomic level, on composite performance. Although nanomaterial agglomeration is conventionally considered undesirable, we show that, near nanotube percolation, clustering of nanotubes can lead to better matrix hardening and higher permittivities, leading to improvements exceeding 30% in the piezoelectric response compared to non-agglomerated architectures. We further demonstrate that although atomic vacancy defects in nanotubes effectively soften the matrix, this can be compensated by agglomeration of nanotubes at larger length-scales.