Suppose the universe was completely empty except for a rotating planet with a moon in geosynchronous orbit. How would it be possible to understand why the moon did not fall since there is nothing to compare the rotation of the planet to.
What is there to understand? Mechanics explains what happens at all circular orbits whatever their radius - whether it is below the geosynchronous radius, above it, or right there. We do not need to compare rotation to anything external, the behaviour of the Moon and other falling objects would be enough to determine that there is some force pushing the Moon away from the Earth.
Would an observer not see a moon levitating above a planet? How would the observer be able to understand what is happening here?
Yes, geosynchronous orbit means the moon stays above the same point on Earth's surface. Description of what is happening depends on the frame.
In Earth's frame, Moon experiences gravity force, and centrifugal force. Since Moon is at rest in this frame, the Coriolis force is zero, and thus the first two forces cancel each other. So on geosynchronous orbit, centrifugal force has the same magnitude and opposite direction to gravity force. By measuring the distance to the Moon, we could calculate the centrifugal forces and from $F=m\omega^2 r$ we could determine $\omega$, angular velocity of rotation of the Earth.
In inertial frame, both Earth and the Moon rotate around common center, and this motion is completely explained by Newton's law of gravity.