Lydia's Heart is a game in the class of Anchorhead, Mulldoon Legacy, Curses!, and Worlds Apart in terms of size and story. To see the size of the game, check out the provided map, and realize that 90% of the rooms have their own detailed puzzle.
First, the story. You play a young girl at a southern motel who is entrapped in the mysterious plottings of a cult. You must find a way to escape their clutches. There are twelve or more NPC's, each of which can be asked numerous questions. The twelve NPCS's are mostly static, but later they move about a bit. The workings of the cult are explored in great detail, both at the motel and other locations.
As for puzzles, they are very, very difficult. This is the same author as Not Just an Ordinary Ballerina, which had very difficult puzzles as well. As an example, there are several locks in the game, which are opened in three or four different ways, two of which are almost never done in IF games. Items must be gathered from far away and assembled into one whole. Characters must be encouraged to move. And some just completely improbable actions must be taken.
However, I took a simple approach; I would just go as far as I could without getting frustrated, then start consulting the hints. The hint system is AMAZING. Just get as many hints as you need. Don't feel bad about it! The author intended this game as more of a story than just a puzzle fest; by consulting the first few hints for each puzzle, you're just making the level of difficulty low enough that the puzzles are still fun, but the story can still progress.
Several reviewers complained about mazes, but they don't realize that sometimes mazes are fun. The author allows you to bypass them with magic words, but then people feel mad about missing 100% completion. I subscribe to a different view; I love stories and settings, and I would rather skip all puzzles in a game to get a good story. Puzzles are fun, but they aren't the reason I play IF (except for Ad Verbum and Praser 5).