Eliezer, this is a wonderful post, but I'd just like to correct a couple of things:

My soul as a computer programmer cries out against the idea of representing N particles with N^2 distances between them; it seems wasteful. ... Also, any position basis invokes an arbitrary space of simultaneity, and a relative position basis does so as well.

You most certainly don't need N^2. For example, in quantum chemistry it's common to use Z-matrices) which have precisely (3N-6) components in 3D space.

As for relativism, why not use relativistic intervals instead of distances? This way you would probably need 8N minus something (probably something=10) coordinates, and you don't even need to arbitrarily choose axes labeled "x,y,z,t".

In the Z-matrix, not all atoms are equivalent, but since it's not unique, it should be possible to find a way to symmetrize it. However, for quantum physics, you probably don't even need to care, because particles are already identical, just make sure your wavefunction has appropriate symmetry.

Finally, your cloud of complex amplitude still has an epiphenomenal factor: the absolute phase. I'm curious to see what would our usual quantum mechanics look like in a representation that would replace absolute phase with some relative coordinate :)