1. Old things (buildings, coins, warships) are frequently found underground. People build over the top of old things all the time.
2. Rule Of Funny. Plus, Bender zapped a couple of buildings. Not the whole thing.
3. The plot demands it.
Last one: No. No, no, no, no, no. Y'see, time and the geological accumulation of matter over everything that sits on the surface of the Earth happens at roughly the same rate over the entire planet.
Let's go back to 1, shall we?
Stuff gets buried over time. Geologically speaking, the Earth is not still. Rock floats on superheated magma, causing it to sink into the core of the Earth at roughly the same rate as it accretes above. And boy, does it accrete. Leave anything in your garden for ten years, and it sinks a little way into the ground. Doesn't even have to be anything heavy. Stuff grows over it, dies, becomes soil, accumulates, and adds to the height of the surrounding ground. Some things may even become completely buried.
This process is going on all the time, everywhere. The rock beneath your feet is sinking into a lake of superheated magma, little bits melting off the bottom and joining that lake. At the same time, the soil over that rock is becoming rock again. Very, very, very slowly. These two things average out so that they're happening at the same speed. ONY is 1,000 years lower than the rest of the world. NNY is at the same level. Obviously, the effect is exaggerated for comedy value. In reality, it will be tens of thousands of years before New York is even a few millimetres closer to that magma lake. Maybe a few hundred thousand.
Now, as the city evolves and changes, certain things will end up being built over. Look at the underground and abandoned levels of Seattle and San Fran. Look at all the buildings, rivers, sewers, and railway lines that used to be on the surface of London, and have been built over. London doesn't seem any higher than anywhere else as a result, but there are two or three stories between the streets you walk today, and the streets that were there three hundred years ago. There's a hell of a lot of distance between the current street level and the cobblestones first laid down by the Romans.
Cities grow upwards over time. As they grow upwards, new street levels are laid down, sometimes significantly higher than the old street level. All these effects combine to produce one common effect: Old stuff is deeper in the ground than new stuff. Unless people still use the old stuff. Then, they tend to keep it accessible, and buildings tend to be easier to use when they're NOT under a ton of soil and rubble.
Futurama exaggerates the hell out of it, but it's still based on the way that things occur in the real world.
This is as much a generalisation as the way that Futurama portrays things. Don't go using any of this for an essay or anything without looking it up... I'm vastly simplifying stuff, being deliberately vague about other stuff (note the repeated use of the word "stuff"), and exaggerating yet more stuff.
But it should hopefully help shed a little light on the answers to your questions.
If in doubt remember the two golden rules:
A wizard did it and Because it is funny.