Moribito should definitely fit your needs. You can also try
Kemono no Sou-ja Erin, another adaptation by I.G and the NHK of a novel by anthropologist Uehashi Nahoko. It streams legally on Crunchyroll as just "
Erin," but the fansub from Static has better translations.
I'm a big fan of
Saiunkoku and Kuwashima Houko (who also voiced Clare), but I can understand why you might find it slow.
The
Hakuoki series is based on an otome game for girls about a young woman who ends up working with the
Shinsengumi. Another role for Kuwashima, but they didn't give her much to do, and she's not an action character.
There's always the Miyazaki film
Mononoke Hime. San is pretty much the character you're looking for as well.
The currently-airing
Rokka no Yuusha has the type of character and setting you're looking for, but it's more a psychological mystery than an action show.