What are some efficient ways to find the differences between two large corpuses of text that have similar, but differently ordered content?
Comparing 2000 paragraphs to 2000 paragraphs is only four million comparisons.

The key to the problem is not to use a function that computes the Levenshtein distance but to use one that computes the Levenshtein distance if the distance is less than a certain threshold, and fails (or, rather, returns +∞) if the distance is greater than the threshold.

This is because you are only interested in closely similar paragraphs. You have no interest at all in the precise distance between paragraphs that are different enough to be unrelated. So as soon as a distance has got high enough to be uninteresting, the function can exit at once; and this will mostly happen very early on indeed during the execution of the function.

The higher the threshold, the longer the running time but the smaller the proportion of false negatives. 

If you know something more about the documents (such as that each paragraph matches at most one paragraph in the other document) then you could make one pass with a low threshold, exclude the matched paragraphs from further consideration, make one pass over your now reduced corpus with a higher threshold, exclude those reduced paragraphs, and so on.

Implementation detail: Presumably you would be calculating a Levenshtein distance on words rather than on characters. If that is the case, you should first assign a number to each word - for example, by sorting the entire corpus, calling the first word '1', the second word '2', and so on. That way your paragraph comparisons would be done by comparing numbers rather than words, which is faster.