To counter performance issues, the easiest thing to do is add tablesample (10 percent) to the query.

This way the newid() function only needs to run on an already randomized sample of 10 percent instead of against the entire data set.

Barry