We present a theoretical study of the solvation structure around an OCS molecule embedded in helium clusters containing 1-100 He-4 atoms, obtained from diffusion Monte Carlo calculations employing an ab initio, vibrational-state dependent internuclear potential and incorporating the molecular rotational degrees of freedom. The effect of the molecular rotation is to make the local helium density around the molecule considerably more delocalized in the ellipsoidal coordinates than that seen around a nonrotating OCS molecule. We find an unexpectedly sharp energy signature associated with completion of the first solvation shell at N similar to 20, suggesting that strongly bound molecules like OCS could have a "magic" quantum solvation number which is not apparent from the structural quantifiers of the solvating adatoms of that shell. The frequency shifts of the asymmetric stretch transition of the OCS molecule are computed as a function of cluster size via a dynamically adiabatic decoupling scheme. The vibrational frequency shows a monotonically increasing red shift with cluster size up to the completed first solvation shell at N similar to 20, where it saturates to a value in good agreement with experimental measurements made for OCS in much larger clusters.