I wonder, why is the cost of synchronizing atomic memory access across all of these threads not higher? It seems like that would cause huge overhead in unfortunate cases - is it up to CUDA programmers to make sure that threads aren't relying on the same memory too often?

I'd imagine so, yes. Just like in any parallel program on a CPU, the programmer should make sure they're not synchronizing so much as to limit the gains from multithreading. For CUDA programmers, the issue is more significant because there are so many threads. But this is not at odds with our understanding of CUDA and its main use, which is to run SPMD programs that perform the same operations on many data and don't need to synchronize too often. If a CUDA programmer writes a kernel that synchronizes too much, then either they should redesign their code, or the problem they're solving is not suitable for a GPU or more generally not suitable for a massively parallel implementation.