I've always found the following argument satisfactory:
Let's say that any mass produces some 'interaction' proportional to its magnitude, which when encountered by another mass produces acceleration proportional to the magnitude of the interaction.
Imagine you've got a one-dimensional space, i.e. a line. In this space, there exists a massive point ##M##, from which interaction propagates in all possible directions. In the one-dimensional space this means the interaction total 'produced' by the point must be split in two, shared between the two possible directions. So if we were to write an equation for the force felt by a test particle ##m## in this 1D space, it'd look like ##F=AmM/2##, where ##A## is some constant. We'd probably want to fold the '2' into the constant, so we'd end up with ##F=BmM##. The force in one dimension is independent of distance from the source.
Now, let's add another dimension. A 2D space is a plane. A massive point on a plane emanates its interaction in all possible directions, which in a 2D space means that it has to be shared between all points of a circle surrounding the point. The circumference of a circle is given by ##2πR##. ##R## is the distance from the massive point. Again, all of the interaction 'produced' by point ##M## must be shared between all points on the circle. We end up with the equation of gravitational force ##F=AmM/2πR##. Combining all constants together, we get ##F=CmM/R## - the force in two dimensions falls linearly with distance.
In three dimensions, the interaction produced by the central point is spread out and shared by points surrounding the point, i.e. on a sphere. Surface of a sphere is given by ##4πR^2##. The equation of force looks like ##F=AmM/4πR^2##. Combining the constants we get: ##F=DmM/R^2##. I.e., in 3D the force from ##M## on a test particle ##m## falls with the square of the distance.
As a final touch, we rename the constant ##D## to ##G##, because it's the initial letter of the word 'gravity'.