armazenar objetos para buscá-los novamente de forma eficiente, evite usar listas

De forma geral, sim. Mas eu diria que depende.

Se a quantidade de elementos é pequena, e se forem feitas poucas buscas, tanto faz. Para poucos dados, tudo é rápido. Lembre-se que um Set possui um custo adicional, já que mantém internamente uma estrutura de dados específica para que as buscas sejam mais eficientes (no caso do HashSet, a documentação diz que internamente ele usa um HashMap). Se são poucos dados e poucas buscas, talvez nem compense - ou não faça diferença - usar Set ou List.

Por exemplo, se a lista estiver ordenada (como já disseram em outro comentário), uma busca binária é muito eficiente (mesmo se tiver 2 bilhões de elementos, no pior caso precisa de uns 30 passos para encontrar qualquer elemento).

Claro que um Set é uma excelente opção para uma grande quantidade de elementos e/ou se tiver muitas buscas a serem feitas (e se precisar de elementos ordenados, ainda tem a opção de usar TreeSet ou LinkedHashSet - o primeiro usa a ordem natural dos elementos, o segundo usa a ordem em que eles foram inseridos). Um detalhe é que um Set não permite elementos duplicados - então se você precisa manter elementos repetidos, aí não tem como escapar de usar uma lista.

Enfim, a grande lição é que toda e qualquer estrutura de dados possui características específicas, vantagens e desvantagens, e o mais importante é entender cada uma delas, e avaliar caso a caso qual a mais apropriada para cada situação (preciso de ordem específica? tem mais inserções, remoções, buscas? etc). No fim vale a famosa frase de Linus Torvalds:

"Bad programmers worry about the code. Good programmers worry about data structures and their relationships."

"Programadores ruins se preocupam com o código. Programadores bons se preocupam com estruturas de dados e seus relacionamentos."

Por fim, vale lembrar que usar System.currentTimeMillis() é uma forma simples de medir o tempo, porém muito sujeita a falhas. Existem formas mais assertivas de fazer esta medição - eu costumo usar o JMH - Java Microbenchmark Harness, mas existem várias outras libs para isso.