Earlier quoted context omitted.
It was algorithms. Back in the 90s there was no AES or ECC. There was RSA, and it was feasible to generate long keys, but it was impractical. Keys from back then could probably be easily factored nowadays. I think the spread of the Internet pushed demand for longer keys and better (more secure and efficient) algorithms.
Just because I was there (I agree with your general point) I wanted to say that I made my first PGP key in 1995 and it was a 4096 byte one, which is just as uncrackable now as it was then. I even remember being vaguely confused, because it gave you options, and I was thinking to myself "wut. Who wants the weaker-than-necessary key. I'll take the big one, thx"
Interesting. How long did it take to sign? Also, though I wasn't sure (which is why I didn't mention it), I thought one of the reasons keys were so short back then was due to the US classifying encryption algorithms as munitions, which made working with actually secure encryption standards difficult for developers. I would have expected the longest key would be 1024 bits, at a stretch. Even that is barely crackable today.