I'll second The Lost Crown. It's horror, fairly new, has a good story and is very long (Took me 30+ hours to complete, while most adventure games are 6-12 hours). Puzzles are about average difficulty in my opinion. I'd say the challenge is just right for a very long, story-driven game, but you'll have to look elsewhere for a game where you'll get stuck every five minutes.