Why do so many PGP public keys begin with
mQINBF? I am just curious.
The first few bytes of the public key packets are describing, among other things, the size of the key and the version of OpenPGP used. As many people are using the same size (such as 1024-bit) and the same version of PGP, it will always give the same first characters. But, it does not mean that the key-space is smaller than expected.
For more information you may take a look at the full specification of OpenPGP messages in the RFC-4880.