I gotta say iv got some old favorites.
Recently, Sword of the Stars was a good game for me.
Before that, the one I liked the most was Imperium Galactica 2, which was my very first 4X RTS.
ANNNNNNNNDDDD WAYYYYYYYYY WAYYYYYY back in the day, back to 1994 or so, maybe earlier, was a game called "Stars!". It was my very first 4X Strategy Game (not RTS), and it was a lot of fun, even though I really had no idea how to play it when I was only 10 years old.

I really looked forward to the sequel "Stars! : Supernova", but that game never materialized due to publishing problems in the UK.
Stars! will probabbly be my most nostalgic favorite, since it was probabbly one of the first, (or at least within the first few years) of 4X Space Strategy games.
After "Stars!", id go with "Star Control : II", but thats more of a 4X & RPG classic. (Its Freeware somewhere out there on the internet, its a great game with voice acting! For 1995 that was insane!)
A buddy of mine also said to add "Tradewars", which was a text based 4X strategy game, but that bored the hell outta me.