A interface Collection representa o conceito mais abstrato, que é uma coleção de objetos. Não se pode assumir nada sobre a ordenação, indexação ou duplicação de elementos.
Já a interface List adiciona posicionamento aos elementos, isto é, cada elemento possui um índice numérico sequencial. Seria uma representação abstrata de um array, com a capacidade (opcional) de se adicionar e remover elementos. Uma classe que implemente esta interface deve implementar, além dos métodos da Collection, os métodos extras declarados na interface List.
A interface Set é um caso onde a única alteração é conceitual, isto é, não é adicionado nenhum método além dos já declarados na Collection. O que a interface faz é expressar um contrato, que é o de não haver elementos iguais (equals()) no conjunto.
E a interface SortedSet estende a Set, adicionando o conceito de ordenação natural dos elementos (Comparable/Comparator), mas ainda assim sem índices.
A interface List é a única que fornece métodos de acesso aleatório (indexado), por isso é a única que possui os métodos get(int) e set(int). Já as outras, permitem apenas o acesso através de um Iterator, que abstrai o percorrimento da estrutura de dados interna.
Tetsuo