Biologi cal cells estimate concentration gradients of signaling molecules with a precision that is limited not only by sensing noise, but additionally by the cell's own stochastic motion. We ask for the theoretical limits of gradient estimation in the presence of both motility and sensing noise. We introduce a minimal model of a stationary chemotactic agent in the plane subject to rotational diffusion with rotational diffusion coefficient D. The agent uses Bayesian estimation to optimally infer the gradient direction relative to itself from noisy concentration measurements. Meanwhile, this direction changes on a time-scale 1/D. We show that the optimal effective measurement time, which characterizes the time interval over which past gradient measurements should be averaged to reduce sensing noise, does not scale with the rotational diffusion time 1/D, but with the square root (rD)-1/2, where r is a rate of information gain defined as a signal-to-noise ratio normalized per unit time. This result for gradient sensing parallels a recent result by Mora et al (2019 Phys. Rev. Lett.) for sensing absolute concentration in time-varying environments.