Tem alguns erros aí. Herança não é quase errado, é certo quando faz sentido, geralmente quando atende o princípio de Liskov. Quando a herança não é adequada então a composição é mais interessante.
É comum, mas não obrigatório que só deveria herdar de classes abstratas ou interfaces, então a herança está certa, até porque herdar delas ainda é herança de alguma forma. O problema é só deve pensar bem se deve herdar de classe concreta, só isso. Em geral quando herda de classe concreta está misturando conceitos e tende a confundir objetos, mas há casos que são exceções, por isso é permitido.
Não é verdade que interface só tem assinatura, pelo menos desde Java 8, portanto há muito tempo isto não é verdade, então você a herda normalmente, antes você herdava o tipo mas não a implementação.
Só dá para modelar objeto de forma correta sabendo todos os requisitos (que quase sempre não são pegos de forma adequada), mas posso dizer que parece que você precisa de uma classe abstrata Pessoa
e não uma interface. Parece que deveria ter uma classe concreta herdado dessa classe que poderia ser PessoaFisica
já que tem um CPF. O CPF não poderia estar em Pessoa
porque uma pessoa pode ser jurídica e não ter CPF.
Mesmo que optasse pela interface poderia ter o método que quisesse. Só não sei se formatação deveria fazer parte da classe que modela uma pessoa. Uma pessoa não deveria formatar CPF, deveria ter uma classe só para formatar coisas ou até o CPF se auto formatar em classe própria, seguindo o SRP.
Não estou dizendo para fazer, mas uma alternativa de modelar de forma mais fácil é esquecer OO, já que é difícil fazer assim, ao contrário do que as pessoas imaginam.
Reuso de código e não "não copiar código" é uma característica de orientação a objeto, mas não exclusivo dela. De qualquer forma parece que leu um material que está dando indicações ruins para você. Por isso eu sempre falo que indicação de material é complicado. Você pode estar lendo um material indicado por um monte de gente e ele ainda ser ruim ou errado. As pessoas aprendem errado com um material e passam indicá-lo como se fosse bom, até porque ela não tem o senso crítico necessário. É fake news por todo lado.
Você ainda está bem longe do entendimento do que é orientação a objeto e não está modelando bem, talvez porque esteja seguindo receita de bolo passada em algum material. Modelar é pensar, é entender o todo. Tem umas regrinhas, mas não para seguir, é só para orientar. Tem que entender porque elas existem para modelar certo.