Иван Филатов

Random.Next(4) для получения фигурки
Поиск/обход матрицы в глубину/ширину по форме фигурки - т.е. будет 4 реализации, как вхреначить фигурку в матрицу
Проверки на крайние значения, чтобы если осталась одна линия - то фигурки выбираются из первых трех, если 3,2,1 ячейки остались последними.

Начинать с позиции 0,0 и дальше вправо двигаться (алгоритм обхода должен иметь правила куда и как прижиматься, например вправо+вверх.)

Этого должно хватить.

По идее, вы не должны заморачиваться сборщиком мусора.
Он сам знает когда ему проверить, есть ли неиспользуемые объекты и сам их очистит.
Если будете часто его вызывать, в частности GC.Collect, это замедлит работу вашего приложения.

И еще, если у вас 20млн строк - то лучше используйте IEnumerable и работаете с ограниченным количеством строк - постранично к примеру. Тогда проблем с памятью не будет.

random(100) <= 50 - первая очередь
50 < random(100) <=70 - вторая очередь
70 < random(100) - третья очередь

Зачем генерировать long (Int64) значение?
Если ключ long целочисленный - то просто добавляйте записи c MAX IDENTITY + 1