Whether or not a genome is “much better than random” depends upon the fraction that is subject to purifying selection. Neutral theory is perfectly compatible with widespread purifying selection. Therefore, a “random” genome is not an expectation of neutral theory.
Edit: “subject” not “subjective”