We report on Brownian, yet non-Gaussian diffusion, in which the mean square displacement of the particle grows linearly with time, and the probability density for the particle spreading is Gaussian like, but the probability density for its position increments possesses an exponentially decaying tail. In contrast to recent works in this area, this behavior is not a consequence of either a space- or time-dependent diffusivity, but is induced by external nonthermal noise acting on the particle dwelling in a periodic potential. The existence of the exponential tail in the increment statistics leads to colossal enhancement of diffusion, drastically surpassing the previously researched situation known as "giant" diffusion. This colossal diffusion enhancement crucially impacts a broad spectrum of the first arrival problems, such as diffusion limited reactions governing transport in living cells.