One of Age of Wonders games? Wizard Throne and Shadow Magic can both fit to the description.

Lol, you're casting a pretty broad net :D

Yep, AoW2: Wizard's Throne it is.
You start the game near razed human cities and have to gather your first army from human survivors.
I couldn't beat this mission, Fire Wizard's cats literally were tearing my army to shreds time and again. Then I sort of misplaced my disc so I don't know where the game went from there.

Your turn.

And while we're at it, should I go for the Wizard's Throne (which I played only a little and without much progress) or Shadow Magic (which I haven't played at all)? Which one is more balanced, has better story and stuff?

Yup, it is a really difficult mission considering it's the very first one. Ke-Nan campaign from Shadow Magic (and you choose it as your starting campaign) would somewhat fit your description too.

So here is where I got stuck or at least lost interest for long time (I'll return to this game eventually):

Sweet! Now I can protect my base with traps! I won't have to hunt down those stupid agents all by myself. I'll place one here, two there and three more here. Great! Let's plan something else to get some monies... (two minutes later, returning to the base). Where are my traps?! Why can I see only one remaining? WTF?! Has my stupid worker just set off the trap himself? So they work here and don't know where the traps are? WHAT?!
You can think of Shadow Magic as enhanced version of AoW2 so in terms of gameplay it's better. The story of AoW 2 is really nice so I think you should start with it. Some parts of Shadow Magic's story you will only understand after finishing AoW 2. While it's not a big deal, just a few references I still think it's nice to play them in order.

Ahem. Traps? Agents? Why would you hunt them? Are... are you evil? An Evil Genius perhaps?

That's right! This part really pissed me off and I stopped playing for a long time. Maybe it's about time to come back to it...

Is that supposed to be the new game we are guessing? Because I thought Ghorpm won the last round.

In case it is, what's the genre? It doesn't sound like anything I've played.

He did guess Age of Wonders 2. And followed with Evil Genius which, in turn, I happened to be familiar with.

It's an action game with a lot of RPG elements.

EYE: Divine Cybermancy?

No.

Right! I thought when you were talking about the traps, you were still discussing AoW2 and commenting on the gameplay, so when the Evil Genius was referenced, I thought it was just a funny poke at the game, haha! :D

Is it the game with Bowie, where you skip from a body into body when you die?

Nope, no body skipping, your character is quite content with the old one. And speaking of death, if it happens to your character, it's Final.

(And the game you meant is called "Omikron: The Nomad Soul", I believe. I have to admit, it does have some interesting features, especially considering its release time.)

A slight hint: the player character in not exactly human.

Yep, I meant Omikron but couldn't remember the name of the title!

Hmmm....what other actions games with RPG elements and not so quite humans are out there?

Hang on, is this Vampire: The Bloodlines? Probably not as you don't go into China in the game, however there is the Chinatown part.

Bingo. And the starting hint was a reference to this.
Your turn.