This is The Quickening by Michael Bishop, which won a Nebula Award for Best Novelette in 1981. I apparently read it in Universe 11, edited by Terry Carr, which also includes another story that I asked for help to identify (Mummer Kiss by Michael Swanwick). Joachim Boaz reviewed The Quickening in an online book review.
In my OP I said, "A man wakes up without memory in a city that is strange to him. Everyone else is in the same situation."
In his 2014 review, Boaz wrote,
The plot’s simple, though how it develops works better if left unspoiled so I won’t say too much about it. The protagonist, Lawson, is an ex-air force man now working in Veterans Administration in Lynchburg, Tennessee. He’s married with two young children, three and five. It’s a normal life, until one morning he wakes up on the banks of what he quickly recognises as the Guadalquivir river, in Seville, Spain. All around him are the moans and cries of other people who just woke up the same as he did, alone and very far from home.
I misremembered the memory loss. People's memories are intact, but they are confused and have no common language. There is no explanation of how this has been effected:
Someone, God, aliens, who knows, but someone has taken all of humanity while it slept (even though there’s never a time when everyone is asleep) and shuffled it. Seville is filled with people from every nation, randomly assembled and distributed. All the evidence suggests everywhere else is the same, all of humanity gathered up and scattered across the world regardless of where they originally came from.
I wrote that I considered this to be a subtle story. So did Boaz:
As a tale of culture shock and social collapse The Quickening works well, but that alone probably wouldn’t have won it the Nebula. Where it really excels is in its subtler aspects.
It was a haunting story. I must have read it some 38 years ago, but the effect has stayed with me.
What really works though is the lingering effect of the book. I can’t say why without massive spoilers, but as the bit above about the indifference to children hopefully illustrates there’s more going on here than mere displacement, we’ve been broken in order to be made new.
I wrote, "Without leaders they set to work dismantling the monuments of the past. He is part of a crew that is dismantling a cathedral. It becomes evident, to the reader if not the man, that the interred remains of Christopher Columbus are being discarded along with the rest of history's baggage. Perhaps humanity is being given a fresh start."
Boaz did not give any spoilers, but he did mention that the setting of the story was Seville. And Seville is where the tomb of Christopher Columbus reportedly is, in the Cathedral.
[UPDATE: "A crew of silent laborers, who worked very purposively in spite of their seeming to have no single boss, was dismantling the Plaza de Toros ... Other crews about the city were carefully taking down the government buildings, banks, and barrio chapels that no one frequented anymore, preserving the bricks, tiles, and beams as if in the hope of some still unspecified future construction. ... It would hurt like hell to destroy the cathedral, and it would take a long, long time -- but, considering everything, it was the only meaningful option they had. Lawson raised his pickax." End of story.]
Thanks to John Rennie for help with identifying Mummer Kiss in the same anthology. That was the clue that unlocked the puzzle. Apologies to the community for an OP that was so sketchy as to hide the identity of a Nebula-winning novelette!
