Sin embargo, estoy intentando recuperar n elementos aleatorios únicos para su posterior procesamiento desde una Colección usando la API de Streams en Java 8, sin mucha o ninguna suerte.

Más precisamente, me gustaría algo como esto:

Set<Integer> subList = new HashSet<>();
Queue<Integer> collection = new PriorityQueue<>();
collection.addAll(Arrays.asList(1,2,3,4,5,6,7,8,9));
Random random = new Random();
int n = 4;
while (subList.size() < n) {
  subList.add(collection.get(random.nextInt()));
}
sublist.forEach(v -> v.doSomethingFancy());

Quiero hacerlo de la manera más eficiente posible.

Se puede hacer esto?

editar: Mi segundo intento, aunque no es exactamente lo que buscaba:

List<Integer> sublist = new ArrayList<>(collection);
Collections.shuffle(sublist);
sublist.stream().limit(n).forEach(v -> v.doSomethingFancy());

editar: Tercer intento (inspirado enHolger), que eliminará gran parte de la sobrecarga de shuffle si coll.size () es enorme yn es pequeña:

int n = // unique element count
List<Integer> sublist = new ArrayList<>(collection);   
Random r = new Random();
for(int i = 0; i < n; i++)
    Collections.swap(sublist, i, i + r.nextInt(source.size() - i));
sublist.stream().limit(n).forEach(v -> v.doSomethingFancy());