First time poster here!
I'm now 31 and I've played almost all of Sierra's games since I was a kid (yes even Larry... we were cool back then... and how else do you think I learned how to play Blackjack!)
I loved every moment of these games and they really challenged the mind. They hold a special place in my heart.
However, we should get with the times.
King's Quest is a controversial series due to the loyal fanbase; I know it will be hard to please everyone. But I don't think going for a 2D classic game will cut it this time.
I think going for a 3D (please don't kill me) Mask of Eternity style'd game is the way to go, and adding more classic elements from the older games into it.
Think about it; a POLISHED free roam 3D game with classic item hunt and use mechanics with MINOR or REDUCED action sequences with a little more mature themes/humor would be pretty good if pulled off.
I don't want to feel nostalgic; if I want to I'll just replay the games. I want a new direction.
As far as puzzles, they should be challenging but fair. No dead-ends, but death sequences are ok (to provide a sense of urgency).
The best games this new generation for me were Demon's Souls & Dark Souls, simply because the mechanics of minimal plot, addictive combat, and challenge created a great formula. Every mistake you made was yours and you learned from it.
So putting this philosophy into the new game would surely be helpful.
Sorry for the long post!