There's a lot of factors that go into this, not just city size and composition. If the city is in a ocean current, then it'll probably erode faster than if it's in still water. Likewise, the stability of the ground is a major factor. Cities near to tectonic features (such as plate boundaries, volcanoes, etc.) are probably gonna have some issues.
Furthermore, metal erosion is dependent on what's rusting it. I'm not gonna get into chemistry, but some locations will rust faster than others.
But... Where is the boundary for completely destroyed, anyways? Remember that if it isn't destroyed fast enough, then it'll get fossilized and it'll take much longer to be destroyed.
You've gotta keep eldritch effects in mind, too. R'lyeh is an example of a buried city that's under the protection of cthulhu, so it won't erode like a normal city. And Atlantis has its own deity.
In conclusion
The destruction of your city is heavily dependent on where it is and what it's made of.