I'm with Andy Bonner here:
I guess the key is "cadences are two chords" —are they always, by definition?
The meaning of "cadence" has come to be used in a specific context to denote various combinations of two chords at the end of a phrase, but even in that context it's not necessarily limited to two chords. For example, it would be entirely reasonable to compare and contrast II-V-I cadences with IV-V-I cadences.
Google Books ngram viewer suggests that the term arose in the middle of the 20th century, so an examination of other meanings of "cadence" is probably not necessary to shed light on the phrase. In particular, we can probably reject the hypothesis that the phrase arose before "cadence" took on its specialized two-chord sense; that clearly didn't happen.
So the answer probably lies in the slightly broader sense in which we can speak of II-V-I cadences and IV-V-I cadences. These are common cadential patterns that have slightly different functions.
Now the Andalusian cadence has two: first, a single instance of the four-chord progression ends on the dominant, which as you note is a cadence of an intermediate variety (in functional tonal harmony, at least), whatever your preferred system of terminology. Second, on the repeat, the dominant is followed by the tonic, giving a full (perfect, authentic, normal, what have you) cadence. This of course sets the music into an endless cycle of short repeating phrases, giving us some of the most infectious examples of music from the 17th century onward. Three centuries later, of course, entire genres of popular music were based on this technique, and the words "progression" and "changes" were favored. Interestingly, that style of popular music arose around the same time as the phrase "Andalusian cadence."
would Andalusian Sequence be a more accurate name?
Perhaps so, but people frequently adopt words and phrases that are less than precise.
I would note, however, that there are some inaccuracies in the Wikipedia article. For example, it cites the Lamento della ninfa, where the progression is mostly A-Em/G-Dm/F-E rather than A-G-F-E (while there are occasional F major chords and E7 chords, these are used sparingly for color, so the article's assertion that the basic progression is A-Em-F-E7 is misleading). In general, you will not often find the descending tetrachord harmonized with root position i-VII-VI-V very frequently in classical music before the 20th century because of the parallel fifths.