¿Cómo serializar un objeto + comprimirlo y luego descomprimir + deserializar sin una biblioteca de terceros?

Tienes un error en tu código y la explicación es demasiado larga para un comentario, así que la presento como una respuesta aunque no responda a su pregunta real.

Tienes que llamar a memoryStream.ToArray() solo después cerrando GZipStream de lo contrario, está creando datos comprimidos que no podrá deserializar.

El código fijo sigue:

using (var memoryStream = new System.IO.MemoryStream())
{
  using (var gZipStream = new GZipStream(memoryStream, CompressionMode.Compress))
  {
    BinaryFormatter binaryFormatter = new BinaryFormatter();
    binaryFormatter.Serialize(gZipStream, obj);
  }
  return memoryStream.ToArray();
}

El GZipStream escribe en el búfer subyacente en fragmentos y también agrega un pie de página al final de la transmisión y esto solo se realiza en el momento en que cierra la transmisión.

Puede probar esto fácilmente ejecutando el siguiente ejemplo de código:

byte[] compressed;
int[] integers = new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

var mem1 = new MemoryStream();
using (var compressor = new GZipStream(mem1, CompressionMode.Compress))
{
    new BinaryFormatter().Serialize(compressor, integers);
    compressed = mem1.ToArray();
}

var mem2 = new MemoryStream(compressed);
using (var decompressor = new GZipStream(mem2, CompressionMode.Decompress))
{
    // The next line will throw SerializationException
    integers = (int[])new BinaryFormatter().Deserialize(decompressor);
}

GZipStream de .NET 3.5 no le permite establecer el nivel de compresión. Este parámetro se introdujo en .NET 4.5, pero no sé si le dará un mejor resultado o si la actualización es adecuada para usted. El algoritmo incorporado no es muy óptimo, debido a las patentes AFAIK. Entonces, en 3.5 es solo una forma de obtener una mejor compresión es usar una biblioteca de terceros como SDK proporcionado por 7zip o SharpZipLib . Probablemente deberías experimentar un poco con diferentes librerías para obtener una mejor compresión de tu datos.