Ursula LeGuin has come up in my searching, but I haven't delved deeper yet. On the surface I got the feeling it wasn't quite what I was looking for, but I will check some other works.

Robin Hobb did the Assassin books, right? I am a fan, but not what I'm looking for at the moment. My immediate reading list has some Nietzsche and Russian literature, and I'd like to break some of it up with some fantasy/sci fi that follows the same vein. I'm specifically looking for a fantastical setting, but characters that are just normal people solving normal problems.

So much of what I'm finding is just a reskin of traditional stories. The characters are more down-to-earth but the problems they're facing are still large and dramatic.