To expand on my answer, motion in the vertical direction does not depend upon motion in the horizontal direction. Both balls fall with the same acceleration but they can still do that while having different speeds in the horizontal direction. If the cannon is tilted slightly up or down, the vertical accelerations will still be the same, but the ball will now take a longer or shorter time to hit.
In the monkey gun experiment, you can drop the two from different heights and, if you aim the barrel at the monkey, you will still hit the monkey. Neglecting air resistance, of course.
Yes, Galileo was earlier, but this problem would have also been solved easily by Newton, too.
It has to do with the curvature of the earth. That's why they land at the same time (theoretically).