Existential types in C#?

Not possible directly in C#.

You can either drop type safety and have non-generic base interface and use it for "generic" code:

public interface MyInterface
{
    object GetSomething();
    void DoSomething(object something);
}

public interface MyInterface<T> : MyInterface
{
    T GetSomething();
    void DoSomething(T something);
}

Or use dynamic (again no compile time type safety):

foreach (dynamic thingDoer in listOfThings)
{
    dynamic something = thingDoer.GetSomething();
    thingDoer.DoSomething(something);
    thingDoer.DoSomething(something);
}

Or generate multiple versions of the handler and create (possibly with caching) based on type (How do I use reflection to call a generic method?) (Note: that you can't really express "list of arbitrary objects" better than List<object> or List<NonGenericBaseInterface> or List<NonGenericBaseClass>):

foreach (object thingDoer in listOfThings)
{
   // get Do via reflection and create specific version based on 
   // thingDoer.GetType(), than invoke 
   // consider caching "methodForType" in Dictionary by type
   MethodInfo method = this.GetType().GetMethod("Do");
   MethodInfo methodForType = method.MakeGenericMethod(thingDoer.GetType());
   methodForType.Invoke(thingDoer, null);

}

void Do<T>( MyInterface<T> thingDoer)
{
    T something = thingDoer.GetSomething();
    thingDoer.DoSomething(something);
    thingDoer.DoSomething(something);
}

Alternative to reflection is to use Expression tree to build similar code.

Since DoALotOfThingsTwice doesn't depend on T you can wrap it in an Action and store those in the list instead e.g.

public static Action DoSomethingTwice<T>(this MyInterface<T> i)
{
    return () =>
    {
        T something = i.GetSomething();
        i.DoSomething(something);
        i.DoSomething(something);
    };
}

then

var listOfThings = new List<Action>() {
    new MyIntClass().DoSomethingTwice(),
    new MyStringClass().DoSomethingTwice()
};