GAMEPLAN

You’d probably like Escape From Paradise:
http://games.gamesocks.com/Escape-From-Paradise

And …maybe… Agatha Christie: Death on the Nile:
http://games.gamesocks.com/Agatha-Christie-Death-on-the-Nile
(it’s more finding hidden objects than solving murders, but you do interrogate suspects)

Do you like RPGs? There’s a free 2D RPG game called Cave Story that’s excellent.
http://agtp.romhack.net/project.php?id=cavestory

And if you like King’s Quest, you should download ScummVM and play free adventure games using that engine. (Same engine as Maniac Mansion, etc.) Here’s a link to get you started:
http://scummvm.sourceforge.net/downloads.php

Ok, hope that helps…

EDIT: Oops, forgot one game you’d probably like. It’s another free trial game. Dream Chronicles:
http://games.gamesocks.com/Dream-Chronicles
References :

Indigo Prophecy is a game that you would love. It has a great story that keeps you playing it all the way through numerous times. Hotel Dusk Room 215 is another game that you would most likely enjoy if you have Nintendo DS. These are the two in the genre that you expressed interest in that I highly recommend.
References :

I like those sort of games too, and some of the suggestions so far are great (I did really enjoy Vampire: bloodlines but you do have to fight people which I found a bit tricky to start with!)

I would also add the Monkey Island series – a really comical set of adventure games based around pirates.

Discword games – point and click type games where you have to explore the Discworld (created by the brilliant Terry Pratchett). The first one was my favourite for it’s intricacy and beautiful design but it did have some completely illogical ways to solve the puzzles so I would say you will need a walk through at certain points…

Broken Sword series: You play as George or Nico (his French on/off girlfriend) and uncover plots behind a mysterious crime/death etc in each game. I’ve yet to complete the most recent one but have enjoyed playing it so far.

I found all of those games fun and light hearted while having enough puzzles and good interaction to keep me hooked. Plus the good thing about these was you don’t have to fight people.

Although I do really enjoy games like that (Zelda is a prime example of a fab series of fighting & puzzle adventure games!) the games that you mentioned aren’t fighting involved (those that I’ve played anyway!)
References :
http://www.worldofmi.com/

http://en.wikipedia.org/wiki/Discworld_(video_game)

http://www.brokenswordplanet.com/

Try this site
References :
Gaming site: http://forum.innogaming.net/index.php