[booB]

I don't know anything about Hercules, so I won't address any 2D games.

As for 3D, certainly Dreamfall fits your criteria. It is firmly rooted in adventure/sci-fi/fantasy, it has a decent third-person action-game control scheme, and it has an AMAZING story. The only problem is, there isn't a whole lot of gameplay. I'm pretty sure the cut scene time exceeds the gameplay time, and then, a lot of the "gameplay" is simply running from one locale to another. If this is a problem for you, I'd recommend skipping it.

Broken Sword 3: The Sleeping Dragon fits, too... it's similar in gameplay to Dreamfall, there is more actual gameplay, but some of the puzzles can get repetitive, and the story is good but not great (and gets a little silly at times).

If you're looking for more "action" in your games, my best recommendation is Beyond Good & Evil. It has elements of adventure games in it, but it is more of an action game. It uses the same game engine as the Prince of Persia series. It is 6 years old, so the graphics are a little dated, but the art style may make you forget this fact. One of the best story lines I've ever seen in a game, and great dialogue. Plus, there is a huge array of different types of gameplay; it combines exploration, platforming, stealth, combat, racing, inventory puzzles, and even has some FPS and RPG elements at times.