I loved Ico but it's exactly what I had in mind when I wrote the above. Same with Prince of Persia. The exploration is wonderful, and the puzzle-solving was OK. And both games frequently drop into "Oops, monsters have appeared, now I must press X and wiggle the left analog stick until they leave". I tolerated this in both cases because it worked into the story, at least...

What I really want to see is a console adventure game that has no action sequences... and still works.