Secondo me è errato (in entrambi i casi) far implementare Cibo ad Erbivoro.

Erbivoro non è-un Cibo mentre è corretto che Erbivoro è-un Animale.(poi dipende da cosa intendi con Cibo, ma non è chiaro ora). Non è l'interfaccia in sé a turbarmi, ma il fatto che sia chiami Cibo ^^'Dato inoltre che la caratteristica di Erbivoro è di mangiare Erba, io non lo specificherei dall'esterno. Quindi:

codice:
public class Erbivoro implements Animale<Erba> { ... }
Nell'altro caso potresti poter fare una cosa del genere: new Erbivoro<Carne>()... che ha poco senso.