Is the point that the order you pull things out of the
set doesn't matter, so demanding that it behave as a
stack is overly prescriptive?
Right. In fact, there are several parts of the algorithm that are not really fundamental; one is how you pick the pivot, and another is how you perform the partitioning (ensuring that all elements before the pivot are less and all elements after are greater).
Lamport's point is that if you look at the fundamentals of the quicksort algorithm, which are that you must pick a pivot, partition such that smaller values come before and larger values come after, and then at some point later apply the same two steps to the two intervals [start, pivot) and (pivot, end].
Any algorithm that follows that specification will correctly sort the array, and then you can tweak exactly how you do that depending on your constraints. You could do it recursively, you could do it iteratively, you could divide it up into separate threads until you have one thread per processor each of which does the recursive or iterative algorithm on a private work list, you could do a worker pool in which each worker takes intervals from the set of remaining intervals to sort, etc. And likewise, you can tweak how you pick the pivot (picking the first element in the array is usually a bad idea, as it gives worst case behavior for already sorted arrays), and tweak how you perform the partitioning.
Anyhow, he didn't go into this kind of detail, he just pointed out that thinking about the fundamental specification can help get you away from the details of a particular implementation.