The elastoplastic response of polycrystalline metals and minerals above their brittle- ductile transition temperature is idealized here as rigid-perfectly plastic. Bounds on the overall plastic strength of polycrystalline solids with prescribed microstructural statistics and single-crystal plastic strength are computed by means of a linear-comparison homogenization method recently developed by Idiart & Ponte Castañeda (Idiart & Ponte Castañeda 2007 Proc. R. Soc. A 463, 907-924 (doi:10.1098/rspa.2006.1797)). Hashin- Shtrikman and self-consistent results are reported for cubic and hexagonal polycrystals with varying degrees of crystal anisotropy. Improvements over earlier linear-comparison bounds are found to be modest for high-symmetry materials but become appreciable for low-symmetry materials. The largest improvement is observed in self-consistent results for low-symmetry hexagonal polycrystals, exceeding 15 per cent in some cases. In addition to providing the sharpest bounds available to date, these results serve to evaluate the performance of the aforementioned linear-comparison method in the context of realistic material systems.