By about the year 800 I had nearly 250000 characters in my save game and I found that deleting a large portion of the dead ones temporarily fixed the problem. I was able to play for about 100 more in game years before the problem came back. The best solution I can come up with is that Paradox could make the game "ignore" characters after they have been dead for maybe 50 years? The characters that I deleted took up nearly 5000000 lines in the save file so I assume that taking massive amounts of land must also add/take up enormous sizes in the save file.
I tried to replicate this in early game by adding an enormous amount of pops and characters and then annexing many large countries. The game started freezing ~20 years after the start date so I would say that this problem definitely has something to do with large numbers of pops and characters and large land transfers.