Zimerius: The legend of Heroes qualifies pretty much as stepping outside the boundaries. To get in attack range always implements another layer of 'thinking' :p
With that said, i seriously enjoy these recommendations, i haven't really tread the jrpg scene as of yet, outside some FF games which always tend to result in reaching point such as LOTR second book, crossing the deserts and weird ecology with only your best friend annex slave and this very weird dude who's seem to be lost on some badly goin trip....
That escape the mines stuff what was happening in FF XII... Like, you know, really? or that just horrendous wave of mindless slaughter you reach after playing about 50 hours of FFXIII, and such a shame though, i really was looking forward to seeing an end to that story
Sadly, I haven't read LOTR's books, only watched the late 90's/early 2000's movies, so I can't say I'm all familiar with the lore. Still, your description sounds like the usual RPG clichés.
Perhaps, in that sense, the best suggestions I can give from the ones I already listed are:
- The Mary Skelter franchise, as it all happens inside an immense, twisted and maze-like entity known as The Jail, which borrows far more from fairy tales than medieval fantasy, as well as doing an horror spin on dungeon design, which is rare in RPGs.
- The Persona franchise, as it borrows far more from mind concepts (such as dungeons taking the appearance of how a person sees the world around them) than medieval fantasy. And the rare dungeons that do resemble medieval fantasy do have reasons to be like that, instead of simply plagiarizing Tolkien because everyone does.
- LiEat, for similar reasons as Persona, except with a far more fairy tale tone. And you can finish it in one afternoon if you're quick enough or if you're following a guide.
And not limiting myself to simply PC recommendations, I also suggest trying out Parasite Eve for the PS1. It is an horror RPG set in "modern day" New York (technically it happens in late 90's, but far more modern than other RPGs). In fact, from what I remember of it, all weapons the main character, a police officer, uses, are weaponry police still uses nowadays. And story is good and you don't need to read the book it is a sequel to, as the game explains all the important plot points of the book in an organic way.