>And randomizing data doesn't necessarily guarantee that you won't still land on a worst-case starting order (as is the nature of randomness).

This is the beauty of randomized analysis in the worst-cases. The worst-case occurs if and only if the random generator spits out a sorted list. If all permutations are equally likely, a list of n elements has probability 1/n! of coming out sorted = O(n^2).

Even in practice, this is very pessimisstic as it only occurs with a probability of 1/n! and is therefore extremely rare.