Qual a melhor forma (e mais rápida) de se fazer isso?

Pense como usuário, você realmente gostaria de percorrer 1500 linhas em uma ComboBox para encontrar o cliente que você precisa ?
Nestes casos, usa-se componentes de pesquisa, um pop-up que o usuário pode digitar nome ou código, e aí são trazidas as informações do cliente que você precisa.

Ok, faz todo o sentido, mas é exatamente isso que acontece, tem lá esses vários clientes aí ele digita as primeiras letras (geralmente 3 primeiras) e a listagem já cai naquele que ele precisa, então é mais ou menos o que você disse.

rmendes08:

Pense como usuário, você realmente gostaria de percorrer 1500 linhas em uma ComboBox para encontrar o cliente que você precisa ?
Nestes casos, usa-se componentes de pesquisa, um pop-up que o usuário pode digitar nome ou código, e aí são trazidas as informações do cliente que você precisa.

É exatamente isso que acontece com o JComboBox porém você precisaria carregar todos os registros antes para alimentar o JComboBox. Ao invés disso, um simples JTextField não possui peso nenhum adicional. E você só faria a consulta no banco após o usuário já ter digitado o filtro o que por si só já torna a consulta mais rápida. Você ainda pode páginar a consulta afim de que ela fique ainda mais leve.