A character-focused space strategy game would be awesome, but I think it would have to be an entirely different game. There'd need to be a focus on houses/lineages/dynasties over empires, there'd need to be greater granularity of control (systems, ships, fleets, armies, bases, planets, sectors, etc) and intrigue/politics at the center stage, with 4X elements somewhat more at the fringes.
I think there's a lot of great games to be made with a focus on characters, but I don't think Stellaris can, or should, be molded into one. Settings like BattleTech, Dune, Fading Suns or even W40K, would work well as backdrop for such a game. I have a feeling it will work best in a non-generic setting, as the various cultures, houses, organizations, institutions, etc. in the world can be given much more interesting mechanics and relationships, than if it has to work with a completely randomly generated universe.
Another aspect of "regular" space stratey games, including Stellaris, which is hard to mesh with a character-based design is the focus on many different space races and usually with empires divided by race (at least initially). Unless they're simply humans in suits, which is an option I guess. Aliens can still exist, but as non-player elements and not intended to play by the same rules as the core characters.
Leaders and characters in Stellaris still have an important role to play - I really enjoy their inclusion, would love to see them expanded mechanically, but they're a supporting feature for the core gameplay, which is empire management. I would not at all mind certain governments having a downside in being forced to utilize rather poor leaders, characters being more than swappable stat modifiers, etc. Especially the way characters and factions are currently linked could use some work. But I'd prefer a focus on improving the empire management and grand strategy bits over making characters central to Stellaris.
As for the announced changes, I'm very excited, and I think they will make the game better and more suited for future expansion.