How can we avoid redundant interface implementation?

Your problem is classified in two parts:
1) Adequate modeling,
2) Technical aspects of week form of multiple inheritance.

1) Adequate modeling

I think you missing one important principle: if you have 1-3 design options using different technical tools. You cannot just ask "what could be the most suitable design?". It depends on semantic of the members of you terminal classes; if you know the classes and the members, you should fist ask "do I really need them?".

Let me illustrate this. What is IAdult? I don't need it! You need IPerson or just a class Person. A person always has the age and can have null or non-null License. It would cover all people including children. When a child obtains License, the class instance changes. For this purpose, your need LicenseNumber? (nullable type). You don't need age, ever. You need date of birth instead. Having age will cause you to change the instance all the time.

You don't need IEdicated as well. Consider everyone as educated, this is fair. You should create a type Education. All persons will instantiate the instance of this type, but the qualify of education will be changed; so the values in this instance will change (grow, hopefully).

What complexity has left? None! You see, by simple analysis I removed all your needs in multiple inheritance by turning it all into on single base class. I made the picture simpler technically yet more adequate to the real life we're trying to model.

2) Technical aspect of week form of multiple inheritance.

After the model is simplified, let's go back to multiple inheritance from more then one interface, so called week form of multiple inheritance. How to make different implementation in different classes in a way free from a predefined hierarchy of implementation classes? I don't want to use your interfaces anymore. Let's talk about interfaces IFirst and ISecond.

I would suggest using a technique of implementation helpers. Something like this:

public interface IFirst {
    void A();
    void B();
}
public interface ISecond {
    void A();
    void C();
}

public class FirstHelperDetail { }
public class FirstHelper : IFirst {
    public FirstHelper(FirstHelperDetail userDetail) {
        this.UserDetail = userDetail;
    }
    void IFirst.A() { /* implementaion using UserDetail */ }
    void IFirst.B() { /*...*/ }
    FirstHelperDetail UserDetail;
}

public class SecondHelper : ISecond {
    public SecondHelper(System.Func<string, bool> userPredicate) {
        this.UserPredicate = userPredicate;
    }
    void ISecond.A() { /* implementaion using UserDetail */ }
    void ISecond.C() {
        if (UserPredicate != null) { /*...*/ }
        //...
    }
    System.Func<string, bool> UserPredicate;
}

class User : IFirst, ISecond {
    internal User(/*...*/) {
        FirstHelper = new FirstHelper(new FirstHelperDetail(/*...*/));
        SecondHelper = new SecondHelper(predicate);
    }
    void IFirst.A() { FirstHelper.A(); }
    void IFirst.B() { FirstHelper.B(); }
    void ISecond.A() { SecondHelper.A(); }
    void ISecond.C() { SecondHelper.C(); }
    IFirst FirstHelper;
    ISecond SecondHelper;
    System.Func<string, bool> predicate = (name) => { /* use name... */; return false; };
}

The sample demonstrate separate techniques of parametrization of helpers. Also, pay attention to explicit form of interface method implementation; this style is usually better then public: the method can not be called through the reference as class, only as interface which provide nice isolation. In particular, one can have too methods A of the same signatures. This style of interfacing is of course optional.

—SA