Another vote for Cherryh - pretty much anything by Cherryh. And in the "journey" department, perhaps also look at John Varley's Gaia trilogy (Titan, Wizard, Demon)? (Probably falls into your "excessive violence and some smut" category)
You might also try the "far future/dying Earth" genre as a way of getting the exploration without necessarily being tied to the space/hard sf milieu. I think the most awarded member of this subgenre (and I liked it quite a bit) is Gene Wolfe's three Sun series (Book of the New Sun, Book of the Long Sun, Book of the Short Sun).
Stephen's Sausage Roll.
I play a lot of puzzle games. Some of them are pretty hard (the later levels of Tametsi take quite a while to crack).
But this one is on a completely different level. If there is a more brutally punishing sokoban-family game on existence, I have no idea what it might be.
Stephen, if he exists, is most likely condemned to roll sausages eternally in hell, for the sin of making this game.