Common algorithms/strategies for dealing with spatial relations

For the collision of equally sized units I went with the Nordeus demo's approach and partitioned space into a uniform grid.
For larger units I would just introduce another grid of higher cell-size. The hashing of positions takes about 0.1ms for 10000 or so units, whereas the actual collision handling takes about 8ms currently.
So generating one or two more MultiHashMaps hierarchies (Bounding Volume Hierarchies) seems to be a sensible choice (I hope).

However I am unsure how to handle attacking of the units now, or more generally speaking checking a bigger neighborhood. I could certainly do it like Nordeus and use the same collision detection to find suitable targets. Or go a hierarchy higher and check a bigger neighborhood, but that likely becomes performance intensive quickly. Aborting after finding the first valid target seems to be a immediate solution, but the way entities are structured into chunks, it seems such a strategy would deliver the same valid first find in every iteration?
I cant think of an immediate way to randomize the outcome of this iteration.

I'm quite interested to learn about commonly deployed strategies on how to handle this.

Another Issue I have is checking multiple scales of neighborhood.
This is more about encapsulating my games logic though.
I would like to have one separate job for collision handling (close), another for melee attacks (medium) and one for ranged (far) attacks. But everything checking spatial relation should likely go in the same job that already iterates my Entities and checks against the MultiHashMap(s).
I guess I could cache the results somehow (How? Per-entity buffer sounds dangerous with thousands of units.) and pass it to separate systems. But that sounds like a performance loss just for cleaner code.
So how would I go about capsuling my actual system logic.
Is there a efficient way to design this?