I don't know if it's free/libre or not, but since Trisquel has it in the repositories, here's my suggestion on space-related exploration game:
Colobot: a game where you can program your own robots to explore the fictional planets of the game. Story mode is very challenging and interesting. Although I haven't played it for a while.
