We investigate the curvature-dependence of water dynamics in the vicinity of hydrophobic spherical solutes using molecular dynamics simulations. For both, the lateral and perpendicular diffusivity as well as for H-bond kinetics of water in the first hydration shell, we find a non-monotonic solute-size dependence, exhibiting extrema close to the well-known structural crossover length scale for hydrophobic hydration. Additionally, we find an apparently anomalous diffusion for water moving parallel to the surface of small solutes, which, however, can be explained by topology effects. The intimate connection between solute curvature, water structure and dynamics has implications for our understanding of hydration dynamics at heterogeneous biomolecular surfaces.