Random sampling of tuples
Using consecutive outputs from the PRNG to form a tuple is fine if you use a good enough PRNG.  So, one reasonable approach is to simply use a good PRNG, and then not waste brain power worrying about issues like this.

One way to get a "good enough" PRNG is to use a cryptographic-quality PRNG.

RANDU is a truly lousy PRNG (for instance, the least significant bit of its output is not random at all), so no surprise that all sorts of bad things happen when you use its output.  But the root cause there is not using tuples from RANDU; the root cause is using RANDU.