It's also obvious as f that any universe would inevitably have key, important, famous individuals as those will inevitably exist at any scale. Look at world history -- we've gone from millions to billions, but we still have key individuals ("heroes") viewed as shaping the world and their era.
More to the point, you're overlooking the potential for a meaningful private sector and underworld. There is no sense of a living universe in this game. It's just a bunch of monolithic empires slamming doomstacks into each other and mining planets. Of course, I'm getting the sense you guys are more asocial number-crunching gamer types than "emergent story" fans, so you're kind of a new market for Paradox and not the ones who have traditionally played games like Crusader Kings and Victoria.
The lack of a private sector is a valid criticism, and me and many others in this forum have written in great detail about how we would like to see expanded diplomatic features, a bigger role for political factions, and things such as galaxy-wide ideological conflicts and civil wars. But that would still be a macro perspective on history, focused on grand historical processes, not on individuals, and certainly not featuring any clandestine visits to seedy space bars or the hiring of legendary assassins with jetpacks.
As far as emergent story goes, I must most strongly disagree with you that it is lacking in Stellaris. This game has provided some of the best emergent stories I have ever had, which is why I still play it. They are a different kind of story, more like national epics (and in that sense very similar to those from Victoria), than the kind of personal story you would get from CKII. Just because a nation/people are the main protagonists of a story doesn't make it less valid as a story.
Stay a while and listen, and I could tell you about the decadent slaver species that had to genetically engineer greater tolerance into itself and abandon slave-holding or face the wrath of a powerful and "tolerant" fallen empire, or of the strict isolationists who ended up ruling the galaxy because nobody would leave them alone, or of the feudal space realm that vassalized one empire too many and lost everything in a subsequent uprising. Just in my most recent game I had democratic liberators go full empire after the ruler became the immortal psionic Chosen One, and then in their hubris they accidentally the entire galaxy by opening up the L-Gate earlier than anyone was ready for and unleashing something terrible that scoured the galaxy of almost all life, leaving only the old fallen empires intact. If those aren't stories, I don't know what are.