It seems paradoxical that the strength of so many phenomena (Newtonian gravity, Coulomb force) are calculable by the inverse square of distance. 

However, since volume is determined by three dimensions and presumably these phenomena have to travel through all three, how is it possible that their strengths are governed by the inverse of the distance squared?

The gravitational force and intensity of light is merely 4 times weaker at 2 times the distance, but the volume of a sphere between the two is 8 times larger. 

Since presumably these phenomena would affect all objects in a spherical shell surrounding the source with equal intensity, they travel in all three dimensions. How come these laws do not obey an inverse-cube relationship while traveling through space?

This is not paradoxical and it is not necessary for any physical phenomenon to a priori have to obey any particular law. Some phenomena do have to obey inverse-square laws (such as, particularly, the light intensity from a point source) but they are relatively limited (more on them below). 

Even worse, gravity and electricity don't even follow this in general! For the latter, it is only point charges in the electrostatic regime that obey an inverse-square law. For more complicated systems you will have magnetic interactions as well as corrections that depend on the shape of the charge distributions. If the systems are (globally) neutral, there will still  be electrostatic interactions which will fall off as the inverse cube or faster! The van der Waals forces between molecules, for instance, are electrostatic in origin but go down as $1/r^6$.

It is for systems with a conserved flux that the inverse-square law must hold, at least at large distances. If a point light source emits a fixed amount of energy per unit time, then this energy must go through every imaginary spherical surface we think up. Since their area goes up as $r^2$, the power per unit area (a.k.a. the irradiance) must go down as $1/r^2$. In a simplified picture, this is also true for the electrostatic force, where it is the flow of virtual photons that must be conserved.
