Above: Newton's classic drawing of a cannonball fired horizontally from the top of a tall mountain. As the cannonball's speed increases, it travels farther from the mountain before hitting the earth. Eventually, the cannonball moves so quickly that the curved earth drops away beneath it and it never hits the earth at all. The cannonball then orbits the earth.
The first situation is simply an approximation, one that only applies to objects that don't travel very far as they fall. When you drop two such objects simultaneously, they both fall together even if one of them has an initial horizontal velocity.
The basis for this approximation is that an object's horizontal motion has almost no effect on the downward force gravity exerts on it, so the object's vertical fall proceeds independently of its horizontal motion. That's why the bullet you drop and the bullet you fire horizontally both hit the ground at the same moment—they fall together.
This approximation runs into trouble when one of the objects you're considering moves so far during its fall that the direction of gravity changes. Gravity always points toward the center of the earth, so two people at distant places on the earth's surface will find gravity pointing in somewhat different directions. A horizontally fired bullet that travels far enough during its fall will find that gravity pulls it in changing directions so that its horizontal and vertical components of motion are no longer independent. This long-distance bullet won't necessarily hit the ground at the same time as one that's just dropped.
But the earth's curvature is also important. Once an object travels far enough horizontally, it will find that the earth has curved away beneath it and it will have to fall extra far before it reaches the ground. In the case of the Space Shuttle, the Shuttle travels horizontally so fast that the earth curves away entirely. In fact, the changing direction of gravity bends the Shuttle's path into an elliptical curve so that it never reaches the earth's surface at all.
Answered by Lou A. Bloomfield of the University of Virginia.