Gravity Sorts
Gravity is a kind of mindless sorting machine. It's not a perfect sorting machine, but when you have objects that can slide past each other easily, it does a pretty good job. The way it sorts is by pulling on objects based on their density. The densest objects collect at the bottom. The lightest objects "float" to the top.
Your question is very much like asking this: "If I hold a brick in the air, and then I let go of the brick, why doesn't the air under the brick cause it to levitate?" This might seem like a silly question, but it contains some important insights. First, the brick and the water scenarios are different, because air is highly compressible, whereas, water is mostly incompressible. But they are similar because both air and water are very slippery. It's extremely easy for air and water (and fluids in general) to move around in response to forces. So when you let go of the brick, gravity pulls it down. But it's also pulling on the air underneath the brick! So why does the brick "win"? Well, it's because the brick has a higher mass per volume, so when gravity pulls it down, the brick is able to push aside the air.
Bricks Float
Now, the same story also works for water. Drop a brick in water, and it will fall to the bottom. Or does it? That depends on the brick, doesn't it? If the brick is made of plastic and filled with air, then it doesn't fall to the bottom, does it? Because the walls of the brick trap the air in a fixed volume, and because they are solid and don't move around much, the average density of the hollow plastic brick can be much less than water, causing the brick to float.
Now, we can say that the water is pushing up on the brick, but a more useful statement is that gravity is pulling down on the water. When gravity "weighs" the volume of water taken up by the brick, and compares it to the mass of the brick, it says: "Well obviously, the water weighs more", so it pulls the water down more strongly. And thus, the brick is left high and dry (mostly).
Bottles are not Fountains
If you have an open container filled with a fluid (not a superfluid!), the fluid doesn't spontaneously leak out the top (unless it's under pressure, but let's assume STP). Again, we should not be surprised by this, because fluid isn't really trying to push up. In both cases, fluid is being pulled down by the earth's gravity. It's just that if you submerge something in the fluid that is less dense than the fluid, then the fluid will get pulled down harder than the object, and result is that the object gets pushed upwards. If nothing is competing with the fluid for space, then the fluid doesn't exert any buoyant forces. Put something into the fluid, and it will most certainly flow upwards out of the container.
Boats are Lighter than Water
It might seem counter-intuitive that an aircraft carrier or a petroleum supertanker is "lighter than water", but the only way they can float is if the average density of the ship is less than water. Since most of a ship is hollow and filled with air, it doesn't matter that we build them with very dense, thick steel hulls. The air lowers the average density enough to let the boat float. Of course, a boat is a complicated kind of brick, because if it's working properly, much of the mass is above the waterline. The boat's entire mass contributes to the "effective density", but only the volume below the waterline contributes. And that's how we can tell how low the boat will float: it will sink until the volume below the water causes the average density to match water.