A random sequence may not fold at all! I seem to remember a paper that tried this, creating a bunch of random proteins, and checking how much structure they had - I think they were helical bundles, but don't quote me.

The nice thing about stable folds, is that 'nearby' sequences in sequence space - as in, point mutations - are the same fold. If each sequence had a completely different fold, then mutation would be much more destructive. Surprisingly, however, sequences that are far apart in sequence space can also adopt the same fold (convergent evolution).