Let me add to the discussion that the difference between 'random' and 'deterministic' is, in the real world, a pure matter of subjective perception. - Like you said: Some solutions produce "ugly" results while others don't.
In the world I'm referring to, the actual difference between 'random' and non-random is basically only, if the human observer is able to recognize a pattern in the generated output, like some recurring scheme or some other aspect that makes him aware what the output might probably look like in one of the next iterations. The ability to recognize a given pattern depends of course heavily on the oberver's context: Some people may fail to see the pattern behind the sequence
2, 3, 5, 7, 9, 11, 13, 17, 19, 23, 29, while other's are likely to quickly detect it.
Therefor, every cheap off-the-shelf PRNG will easily make the observer/user believe its output is really random. - Or, put in another way: Whenever the observer fails to recognize the cause-consequence (or input-output) correlation in a system his observations will appear as purely random to him.
As I see it, the question then becomes:
- How complex would the algorithm need to be to 'deceive' the (expected) observer?
- How to shape the output in a way that, while remaining perceived basically random, creates the desired 'realistic' or 'non-ugly' perception. - This may also be about aesthetics. Fractal algorithms often are good at this, because their output structurally resembles the observer's impression of the real world.