So here's my answer:

1. In most populated places, about 1000 years. However, I think that many brick, stone and concrete structures would leave visible remnants for even longer, especially where it is dry. Looking at the pyramids, Stonehenge, or the Great Wall of China, it could take several thousands of years with very large structures. NYC would take a long time to revert into unrecognizable rubble, probably 7000-8000 years. It would take a major earthquake or two or some other huge climate impact to get the process really going.

2 & 3. IMO these are probably almost the same. We find plenty of 500 MYO fossils. I have one of a trilobite, actually. Therefore, I think it would take almost a complete cycling of the Earth's crust to completely remove any traces of our existence. The oldest rocks are around 4 BYO, and the oldest fossils are about 3.5 BYO, so I think it would be close to 4 billion years. Basically, everything we leave would have to be subverted and melted.

Of course, as sounds_sound mentions, some of our satellites, the Mars rovers, the moon landing, and the Voyager probes will last even longer. However, they would not qualify for question 2.