It has to do with the curvature of the earth. That's why they land at the same time (theoretically).
You can put a coin on the edge of a table and slide another coin into it so they both fall off. If you hit it just right, one will go out a few feet, the other will fall nearly straight down. They will hit at the same time. Over that short range, the curvature of the earth is not important. Over a large distance, the fact that the gravitational field lines are radial is important.
However, if you could make a gravitational field whose lines of force were parallel, this problem would still work. It also works with charged particles in a parallel electric field made by flat parallel charged plates.