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? Mach's ideas (the need for presence of external material bodies to justify why inertial systems are preferred) are interesting and stimulative, but they are not accepted as part of standard mechanics. Inertial systems are used in mechanics already because it produces useful and accurate theory; there is no real need to base this usage on the presence of distant external material bodies.
Mechanics explains what happens at all circular orbits, whatever their radius is - when 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 the geosynchronous orbit, the centrifugal force has the same magnitude as and opposite direction to the gravitational force. By measuring the distance to the Moon, we could calculate the centrifugal force and from $F=m\omega^2 r$, we could determine $\omega$, angular velocity of rotation of the Earth.
In an inertial frame of the common center of mass, both the Earth and the Moon rotate around this center, and this motion is completely explained by Newton's law of gravity.