This can be avoided in one of two ways, make them aware of each other, so that they can't all be in the same state (like fermions) or raise the temperature, i.e. add randomness. Probably you'll need to do both and find an energy function that's less retarded than choose the first branch you see…
>heterogeneity is your guardian angel - varying the path-finding model a little bit from agent to agent hedges against the resonance structures on display here.
Adding a small amount of randomness (occasional 'wrong' turns) reduces congestion on the major paths that would be the dominant route for agents.
>Additionally, you periodically check the accumulated micros against a macro model and correct gross deviations. Neither step is computationally strenuous.
Every once in a while, check and make sure those wrong turns didn't add up to some agents being way far away from their destinations; if so, turn them in the right direction.
In some situations, a greedy algorithm works well but a totally random one works terribly, in other situations a random algorithm works well but a greedy one works terribly. Combine the two, and everything works out well enough to be plausible under all circumstances.
A popular load-balancing strategy that finds a middle ground is "best-of-two" routing where you choose two servers at random and route to the one with lower load. There are probably similarly simple ways to introduce variety and randomness into the SimCity agents.
Then, have a global pattern of how everything should be working, more or less. When a major deviation is found from the global pattern, adjust. How exactly? Those are implementation details.