Shalom Moshe
Your statement below describes a model I have been thinking about for some years - a face-centered-cubic universal lattice:
You wrote: "To see the tension between this requirement [Lorentz invariant at the Planck scale] and fundamental discreteness, imagine at first the most naive possible discrete model, the assumption that our space is arranged into a cubic lattice of sides whose length is precisely lp. It is immediately clear that this statement depends on your reference frame, your friend in possession of the latest spaceship model will zoom by this lattice and will see it Lorentz contracted. The principle of relativity is clearly at odds with this very naive picture."
My short response is that the cubic lattice will not be seen from the spaceship, let alone contract because it is not itself made of matter nor does the lattice constitute a frame of reference! The lattice has no background in which it is embedded - it itself creates space, matter and everything else. My other observation about this very basic and important picture you conjured is that in such a lattice the spaceship will not move as if it were in an inertial frame, but will self-convolute as a soliton pattern leap-frogging across the field of lattice nodes, as I have outlined in my original Beautiful Universe paper on which my present fqxi paper is based.
I hope this makes sense and that it helps. Vladimir