One of the most common expectations of a quantum theory of gravity is that spacetime is uncertain or fluctuating at microscopic scales, making it a stochastic medium for particle propagation. Particles traversing this spacetime may experience fluctuations in travel times or velocities, together referred to as lightcone fluctuations, with even very small effects potentially accumulating into observable signals over large distances. In this work we present a heuristic model of lightcone fluctuations and study the resulting modifications to neutrino propagation, including neutrino decoherence and arrival time spread. We show the expected scale of such effects due to "natural" Planck scale physics and consider how they may be observed in neutrino detectors, and compare the potential of neutrinos to.-ray astronomy. Using simulations of neutrino mass states propagating in a fluctuating environment, we determine an analytic decoherence operator in the framework of open quantum systems to quantitatively evaluate neutrino decoherence resulting from lightcone fluctuations, allowing experimental constraints on neutrino decoherence to be connected to Planck scale fluctuations in spacetime and.-ray results.