But the first season may be worth it? Hmm…
I’d recommend Fullmetal Alchemist. It’s very much fantasy, it essentially takes place in a world where alchemy works like the more… optimistic philosophers thought it did and we studied that instead of physics. It seems a lot like a typical vapid action anime at first, but there are several very morally complex, or just plain heart-wrenching situations. In some ways it’s very much a war drama, where you see military officials reacting to a system they slowly realize has been corrupt from more or less the beginning (and that’s an understatement).
As for the “atypical for your average stupid action shonen anime” things, here’s one early episode
The main character, looking for information on the philosopher’s stone goes to visit Shao Tucker, the only man to make a chimera (animal hybrid) that can talk. Over the course of the episode, it becomes clear that his wife disappeared around the same time he made the Chimera. This year, if he doesn’t make similar progress he’s going to lose his job. And suddenly both his very, very young daughter and his dog disappear while another talking Chimera mysteriously appears. And no, it doesn’t end well, it doesn’t just “go back to normal.” They do not fix it, they only do which they can which basically boils down to getting revenge, and they kind of even fail at that.
Either FMA:Brotherhood or the original anime are equally very good. They’re pretty much the same, save for minor differences, until one point in about the first or second season (out of four or so seasons for both I think) which is where the original anime caught up to the (still in production at the time) manga and went and did their own thing instead of resorting to filler.