How to serialize object + compress it and then decompress + deserialize without third-party library?

You have a bug in your code and the explanation is too long for a comment so I present it as an answer even though it's not answering your real question.

You need to call memoryStream.ToArray() only after closing GZipStream otherwise you are creating compressed data that you will not be able to deserialize.

Fixed code follows:

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();
}

The GZipStream writes to the underlying buffer in chunks and also appends a footer to the end of the stream and this is only performed at the moment you close the stream.

You can easily prove this by running the following code sample:

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 from .NET 3.5 doesn't allow you to set compression level. This parameter was introduced in .NET 4.5, but I don't know if it will give you better result or upgrade is suitable for you. Built in algorithm is not very optimal, due to patents AFAIK. So in 3.5 is only one way to get better compression is to use third party library like SDK provided by 7zip or SharpZipLib. Probably you should experiment a little bit with different libs to get better compression of your data.