Eu tenho uma classe genérica e quero impor que as instâncias do parâmetro type sejam sempre "convertíveis" / conversíveis em String. É possível fazer isso sem, por exemplo, usar uma interface?

Implementação possível:

public class MyClass<T> where T : IConvertibleFrom<string>, new()
{
    public T DoSomethingWith(string s)
    {
        // ...
    }
}

Implementação ideal:

public class MyClass<T>
{
    public T DoSomethingWith(string s)
    {
        // CanBeConvertedFrom would return true if explicit or implicit cast exists
        if(!typeof(T).CanBeConvertedFrom(typeof(String))
        {
            throw new Exception();
        }
        // ...
    }
}

A razão pela qual eu preferiria essa implementação "ideal" é principalmente para não forçar todos os Ts a implementar IConvertibleFrom <>.