Would it be possible to add sand and smaller bits of rock as you are creating the foam dealio? Add a layer of foam, then a layer of rock and sand, them more foam? It could add weight if not completely keep it submerged. I have yet to work with the foam stuff, so I have no idea.
As far as connecting PVC legs to racks, could you integrate the PVC legs and racks (PVC legs attached to PVC cross members) connected to shelves with zip ties, and then foaming the entire structure to protect from UV as well as hide it? Could you also hollow the foam structure out to detract from the buoyancy?
Nice idea with the milk crate, btw.