I'm surprised this wasn't brought up in a post before mine but all through listening to this podcast episode and reading this thread, one game in particular strikes me as 4X but so very, very different than the pack:
Space Rangers 2: Reboot
Maybe others don't consider it 4X? Its certainly meets the criteria for Explore, Expand, Exploit, and Exterminate, it just so happens you just control a single space ship captain, not a whole empire. Please, do yourself a favour, check it out, at least watch a Let's Play of it for a bit or something to that effect. It even has a RTS and text adventures in it for when you need a break from trying to be the best Ranger that saves the universe. And you better be strategic in your decisions or you will end up vapourized.
Surely there are other games that might be considered 4X but have given it an enjoyable twist. How about something like FTL, Space Pirates and Zombies, or Starscape, could any of those be considered 4X even though they may not be as high up the strategic scale as empire builders? You do have to be careful in selecting your next destination for its strategic value in these games.
And if you want a recognizable thematic property that would put more life into its space tech than just "Lasers mk3 +3", look no further than shamelessly ripping off Firefly (or good luck acquiring the rights).