Well, I checked your PC list. Checked GOG... You pretty much have the entire catalog already xD Everytime I thought I had the game for you, either it was already on your list, or is not on GOG, or it costs 9.99. So I'm not in I guess.

I will leave my recommendation nonetheless, and that is Rune Classic. You like adventure games, you like action games, and you like RPGs. Well, take the "epic story" from an RPG, the dungeons and platformers out from adventures, and the action of an FPS (only in 3rd person) and you get Rune (and the Halls of Valhalla expansion). Here on GOG you have the game and it's expansion. You have a great story (not sure about the expansion though) trying to stop an evil viking from bringing Loki back to life so that it can unleashed Ragnarok (and two endings), great gameplay with mouse and keyboard (like a third person shooter except with melee weapons) and awesome soundtrack. And of course, the monsters in that game are awesome! Not to mentions the game still looks great since it uses the Unreal Engine (I believe the 2nd version, since the game is from the year 2000).

I'm not in but my fave GOG is Betrayal at Krondor. I even wrote a guide about it in the game forum.

Based on all the adventure games you've completed or beat on DS and PC, there is one game that immediately popped into my head that you don't even have yet. That game is The Last Express. It is 5.99.

We seem to have completed similar adventure games. The Quest for Glory games in the unfinished category seems like something you would also enjoy.
In for NWN

Try Dangerous Dave.

It's a classic platformer-shooter with lots of morbid humor. For some reason I've always thought they were similar to Commander Keen. And if you like the game, GOG actually sells the whole series in a pack.

In for NWN and thanks ^^

Not in, +1 and :
When I saw you listed SEGA and SNES games I immediately looked out for two titles. I was relieved to see one of them there, and horrified not see the other.

The one that I saw was : Golden Axe !!
The one that I didn't see was : The Lion King which is an awesome game you should make a mental note of!

Apart from that I would like to recommend two gog titles which I didn't see in your list. Since you tried your hand at 5 of the HoMM games, but didn't finish any, it seems to me that you should try your hand at some fantasy TBS with a different vibe. Two excellent ones :

Age of Wonders 1
Disciples 2

Compared to HoMM, AoW is more like Civilization (although you cannot build cities in the first one, and the combat is more advanced with a tactical view). Of all the TBS games I've played, AoW has left me with the best stories. This one time I was trying to rebuild a dwarven undergound kingdom from a vast network of collapsed underground caverns. With a lot of digging I managed to uncover and rebuild several ruined towns and cities, and after several battles against goblins I finally managed to reach the ruined dwarven captial of the kingdom. Unfortunately, these deeper (there are 3 levels: surface, caverns and deeper caverns) caverns extended far into orc territory, to caves underneath their surface kingdom. When the orcs learned of my presence they unleashed giant red dragons into the caverns, that decimated any rebuilt city or town one happened upon. With all my progress into the deeper caverns ruined, I had to hastily organize defenses for my towns in the caves closer to the surface. Luckily there were only 2 access points from these caves to the deeper ones, and so I could organize small dwarven teams of archers and several ballistas to defend these choke points. As soon as a dragon tried to come up through such a choke point I managed to kill it with concentrated fire. To reclaim the deeper caverns I created dragon hunting parties with the bravest of my dwarf warriors, to brave the deeper caverns and seek out the dragons. Meanwhile, on the surface, I gradually took over a human kingdom, and to earn their trust I captured goblin towns on their borders that I let the humans migrate to. This worked out very well, since it granted me access to their powerful airships and gunpowder units which I needed to defend against the habitual red dragon that came in from the orc kingdom on the other side of a great lake...
More than any other TBS, playing through the game created story after story like this which I remember long after I stopd playing. Here is the menu theme of the game which I think gives an accurate portrayal of the vibe of the game:
Age of Wonders 1 Menu

Disciples 2 is my overall fantasy TBS favorite. It didn't create stories in the same way as AoW, but it has an intense and intoxicatingly dark/grim atmosphere with characters and highly detailed units with dangerous overdoses of badass-ness. Here is, I think, a good review of the game that shows some gameplay:
Disciples 2

Thank you to everyone who participated. There are some good suggestions here, and I'll have to keep an eye on them.

Most of you didn't enter the giveaway, though! I suppose that does make it easier for me to pick the winners, though.

Cbob60 didn't specify any game, so by default, Contraption Maker goes to him.

That leaves two contenders for Neverwinter Nights; ruusakraj and popperik - both of your suggestions are good, but The Last Express seems just a little bit more interesting to me, so I'm awarding this one to ruusakraj.

Congratulations to both of you! PMs are going out now.

I want you python database manager :( Seems pretty awesome :)
Sorry way to much game to go trough :P ;)
Random advice: Beyond Good & Evil, it's just good ;)