The balls' height above the Earth is the same for both balls at each time because of the principle of relativity - that is true even in Newton's physics, without all the special effects that occur near the speed of light.
The principle says that the phenomena obey the same laws of physics from a viewpoint of a uniformly moving observer. So if you have two systems that are moving, without respect to one another, in the $x$ and/or $y$ direction, it doesn't change the fact that the "depth" at time $t$ after any ball leaves the desk goes like
$$-z = gt^2/2$$
In some sense, you may imagine that the forces and the laws of physics act on each component of the velocity separately. So the velocity of a ball in the horizontal direction (one of them) has no impact on its motion in the vertical direction.
Just to include an amusing correction: the Earth is not completely flat, after all haha.
Because it is not flat now, the very speedy ball may escape to outer space. The principle of relativity doesn't hold anymore: the presence of the round Earth distinguishes objects that are at rest with respect to the surface from those that move horizontally. It's because if you move the whole physical system in a linear direction, the background looks different because the Earth changes its location. This wasn't the case for the flat Earth which was invariant under horizontal translations.
More precisely, you may still introduce a principle of relativity, but with an extra correction. You may use two frames - one that is static with respect to the Earth and another one that is rotating around an axis through the Earth's center exactly in such a way that the speedy ball will look like a ball at rest. However, the laws in rotating frames are not quite identical to the laws in the inertial frames. Fictitious forces have to be added.
In the second, rotating frame, however, there is an additional force - the centrifugal force - that needs to be added to the laws of physics. Because of this centrifugal force, the speedy ball is able to escape from the gravitational field while the slow ball is not. More precisely, there's a centripetal force (into the center) that acts on the ball at rest - which is moving in the rotating frame - and this centripetal force keeps the (originally) slow ball in the Earth's gravitational field.