Olá Alisson, tudo bem com você?

No segundo caso, não é preciso informar pois o tipo do titular da Conta (nesse caso, contaDoPaulo) já foi definido dentro da própria classe Conta:

public class Conta {

    double saldo;
    int agencia;
    int numero;
    Cliente titular;

    // codigo omitido
}

Em outras palavras, o Java sabe que contaDoPaulo.titular deve receber algo do tipo Cliente de acordo com o que declaramos dentro da classe Conta. Então quando o Java lê o contaDoPaulo.titular, ele vai até a classe Conta para consultar qual é o tipo que o titular deve receber. Diferente do primeiro caso onde tivemos que deixar explicito que o tipo da variável paulo seria Cliente já que, caso contrário, o Java não teria como descobrir seu tipo:

Cliente paulo = new Cliente();

Não sei se consegui ser claro na explicação, mas se tiver ficou alguma dúvida é só avisar! ;)

Forte abraço e bons estudos!!