I own Fleet Captains. I love Fleet Captains. But it's not a strategy game. It's a thematic, storytelling game really. No 4x4 gameplay. Also, unless you sink a pretty penny into it for the base game and the expansion, it's a 2 player game. And even with the Romulan expansion, it's 3 player at most. They SAY you can play more, but you're doing teams at that point and the game becomes considerably less fun.
I've played Eclipse 3 or 4 times. It's good and would probably fit the bill. But in my opinion, Eclipse may be a bit daunting for non-board gamers not used to standard board gaming conventions. I would personally recommend Alien Frontiers
for a great, easy to learn game. It's not a space exploration game per se, but it is a space themed game with fantastic gameplay that will take about 10 minutes to teach. It plays up to 4, but there's a cheap mini expansion called Factions that you can buy that will add a 5th player.
If you want a party game that will have your guest alternately laughing and screaming at each other throughout the night, I humbly submit the suggestion for Battlestar Galactica
. It will take all 6 of your guests. It's a game in which you suspect someone of being the enemy, but you never really know for sure until they reveal themselves. It NEVER fails to please.
edit: whoops, didn't see that Kronovan suggested BSG already. Great minds think alike!