Why do more complex DNA strands take longer to anneal?
What is meant by complexity?
This is the crux of the matter. As is often the case, confusion arises from not defining one’s terms. In this case the three possibilities we have to deal with are:

The extent to which a sequence is not homogenous. e.g. ATATATAT is more complex than AAAAAAAA; ATGCATGC is more complex than ATATATAT; ATGCTCAG is more complex than ATGCATGC. This would seem to be the definition assumed by the questioner (and also in another answer).
The length of the sequence. This is the definition given in the article quoted in the question: “Complexity - the total length of different sequences”. However it is not one that would have occurred to me on encountering the expression.
The extent to which a length of DNA (especially a chromosome) has regions present in multiple copies. This seems not to have been considered in the question, but is historically what was meant be genome complexity deduced from annealing experiments. This is shown in these extracts from a venerable text on nucleic acids, long out of print:


In human cells unique DNA has a Cot1/2 value of 1000 (moles nucleotide seconds litre–1)…Repetitive DNA includes all of the rest of the DNA. Among the repetitive DNA is a fraction which reanneals with a Cot1/2 value of between 100 and 1000…thought to be those [genes] coding for proteins which form major structural components of the cell… [some examples given of multi-copy genes like tRNA]…At the other extreme DNA with a Cot1/2 value as low as 10–3 consists largely of satellite DNA.

Explanation for Case 3 (complex because of multiple copies)
As the article quoted in the question correctly states, “Renaturation, or duplex formation requires random collisions between two single-stranded molecules”. However such experiments are performed with fragmented DNA in solution, not whole chromosomes, so the two molecules that must collide are gene-size or smaller in length. The more copies of geneX or sequenceX there are in the DNA, the greater the number of targets there will be containing geneX or sequenceX, hence the faster fragments containing such genes will anneal.
Explanation for Case 1 (complex because less homogeneous)
Assuming that one is comparing single-copy genes of different degrees of homogeneity, one can imagine that for something like ATATATAT there will be more ‘hits’ that give partial overlaps that may be detected as double-stranded:
A T A T A T A T A T A T A T A T
        T A T A T A T A T A T A T A T A

Alternatively, once bound imperfectly, there may be a greater chance of perfect binding after dissociation because of proximity.
However, it is also possible that writers are confusing or amalgamating this with Case 3, as simpler DNA may actually be present in more copies in a genome.
Explanation for Case 2 (complex because longer)
The explanation here is trivial. If you perform reannealing experiments with two geneomes — E.coli (4.6 Mbp, c. 4000 protein-coding genes) and Carsonella ruddii (0.16 Mbp, 182 protein-coding genes) — employing the same amounts of DNA as 300bp fragments, the fragments from the smaller genome will be approximately 20x more likely to make a random collision with a complementary fragment.