It sounds like Andre Norton is right up your alley. Interesting and likeable outsider characters, large conflicts and the fundamental questions of life are what she does best.
Her Witch World series is either sci-fi or fantasy depending on which books you're reading, which I thought was neat.
I think you'd especially like the first part of the Estcarp Cycle, the Gryphon trilogy and Year of the Unicorn.
Estcarp Cycle:
Witch World (1963)
Web of the Witch World (1964)
Three Against the Witch World (1965)
Year of the Unicorn (1965)
The Crystal Gryphon (1972) – first book of Gryphon trilogy
Gryphon in Glory (1981) – second book of Gryphon trilogy
Gryphon's Eyrie (1984), with A. C. Crispin – third book of Gryphon trilogy
She also did an excellent sci-fi series called Time Traders about humans who discover time travel technology and an alien invasion. The first few books are out of copyright on Project Gutenberg:
http://www.gutenberg.org/ebooks/author/7021
The Time Traders
Galactic Derelict
The Defiant Agents
Key Out of Time
Firehand
The Deed of Paksennarion is also a great series. The heroine is a genuinely good woman who rises from a farm girl to - well - you'll see. I loved the thoughtful and intelligent worldbuilding and how very real everything felt - the aliens were truly alien, even different human cultures were distinctive, and the series slowly builds up to kingdom-level conflict in a way that felt very natural. There's other series set in the same world which were also excellent. Baen has the ebooks, including the omnibus, DRM-free.
Another one you might like is Steven Brust's Vlad Taltos series. It's narrated by a human living in an empire of aliens, and it's a fascinating read. It's got magic and elves, but it's very much got the feel of science fiction because magic is very much simply another technology. The main character doesn't start out likeable, and part of the point of the series is him coming to terms with this and beginning to change.