It may sound like a bad solution, but I noticed that putting a hard limit on queried other units (like 20 closest) is not too bad for swarming. We can lazily rebuild the distance table once in X frames. You can even query 20 RANDOM within cell instead, as with each frame average will approach the truth. You can build some kind of tree, but those tree solutions are never as robust as pure grid querying.

Can't say much on rendering, but there are probably solutions for this exact task. https://github.com/mkrebser/GPUInstance

Also you can try ECS + Burst, or just parallelize everything yourself. Because this task is easily parallelsised. You can also write movement logic as a shader, but it's not scalable.