There was a thread about this topic recently. In essence, you can use shading and shadow to hint at depth. This would be good for small steps of depth, but you are talking about large steps (sky-scraper sized steps) so it might not work quite as well, considering the shadowing is only a hint and not a solid indicator of relative depth. Frankly, by taking a full dimension out of the equation you limit yourself quite severely and if it is vital to your game that players know they are in a city full of buildings ranging from skyscrapers to one-stories, you might want to reconsider your decision as far as viewpoint and perspective.

Or you could just add perspective even if its top down.

So a building at the center will only show the roof, but the buildings at the sides will show their walls.

Or you could just add perspective even if its top down.

So a building at the center will only show the roof, but the buildings at the sides will show their walls.

IIRC this is how GTA 2 worked (http://cdn1.spiele-umsonst.de/gta21.jpg), with buildings in 3D but all the cars in straight 2D.

Overall, I would say that it's very hard to make pure top-down look good, partly because we rarely see anything from that perspective day to day. Even GTA 2 had to stylize the crap out of the cars in the game to make them distinguishable and looking back on it, they still look kind of weird.

You could look into enginnering various "situations" that would allow you to show some depth. As you said, all gameplay is strictly top down, but you could have some bird's eye view fly-ins at the beginning of a level for example. It would be a lot of extra work no doubt... but possibly worth it. If you keep the art style consistent between the fly-in and the gameplay portion it could definitely convey scale that wouldn't exist if you "just" had a flat map. You could have scripted events, like say a boss fight where the boss flies in and smashes through the top of a skyscraper, which you could show from a different angle, maybe you could do it with comic book style panels flashing by, to limit the amount of animation you'd need.

I think the general idea is that you can leave the gameplay relatively flat but use something surrounding the gameplay to bring some more life to your setting.