Necesito "insertar" un elemento en el índice dado en una pequeña matriz. Es decir, para mover todos los elementos con índices mayores 1 lugar a la derecha. ¿Cuál es la forma más rápida de hacerlo en .NET?

NOTA: Agregué mi propia respuesta, pero sigo buscando una explicación y alternativas más rápidas.

EDITAR: Necesito una matriz, no unaList<T> y no una lista enlazada.

ACTUALIZACIÓN: Como no obtuve una explicación de los resultados extraños del rendimiento, hice esa pregunta por separado:¿Por qué copiar referencias a cadenas es mucho más lento que copiar ints (pero viceversa para Array.Copy ())?