Hum, not to sound pessimistic but given your cristerias and what you said you liked, I don't think you'll find what you want, like ever. Unless you do it yourself. Or unless a "breakthrough" happens, like someone with a really good idea creates a new genre and make it work.
Due to "human brain are limited" reason above, designers generally will not put a storyline with heavy RPG elements in a 4X. Also due to 4X and RPG generally interacting poorly. What is currently the closest to that for me is crusader kings and the like but it's more of a "create your own" story, and it's entirely possible to play it only by taking into account game mechanics...
Entirely 3d games space games... same problem. Most people can't handle 3 dimensional combat. Freespace was more of an RPG than most of what's called RPG those days (basically anything with an XP system = RPG..., instead of you know, Role Playing Game). But there is a limit to the number of systems which is set in a game. If you want a deep engaging story with heavy RPG elements most designed will limit "gameplay" options.
There are quite a lot of 2.5d space games with claims of a story, like starpoint gemini, or the space ranger series but labelling them "good"... yeah not often. Evochron mercenary was not stated yet, but does not really have a storyline and companions. Legends of Pegasus is not buyable anymore due to the studio producing it closing (and being full of bugs), but they tried (and failed) to make a story in a 4X.
Last... Star Trek and Star Wars games ? Sadly a lot of them... well. But some are good, like Star Trek Bridge Commander.