D>Может кто-нибудь подскажет алгоритм получше?
По описанию вроде как самая простая рекурсия
Если гарантировано что input.Length != 0 и input[depth].Length != 0 — то что-то такое:

static void seqList(object[][] input, int depth, object[] current, List<object[]> result)
{
    if(depth < input.Length - 1)
    {
        foreach(var oi in input[depth])
        {
            current[depth] = oi;
            seqList(input, depth+1, current, result);
        }
    } else
    {
        foreach(var oi in input[depth])
        {
            current[depth] = oi;
            result.Add((object[])current.Clone());
        }
    }
}

//вызов:
var result = new List<object[]>(input.Aggregate(1, (x,y) => x * Math.Max(1, y.Length)));
seqList(input, 0, new object[input.Length], result);