Thanks for all the feedback, I put quite a lot of great titles on my to-play list.

I managed to find the game, it's Rising Lands. I've attached a screenshot with the building I mentioned (top left corner).

Did you look under the couch cushions? I always find a lot of missing stuff under there.

Released in 97, Gamespot doesn't even have a picture for it.

.... no way ... That is the first time I've laid eyes on that game in about 17 years since I too played the demo. It didn't impress me much though so I am going to go ahead and recommend : KKND!! (not fantasy though but really kickass)

heh Mobygames does! Exactly one - of the title from the FMV intro!
http://www.mobygames.com/game/windows/rising-lands/screenshots/gameShotId,148260/
Judging from that I wonder if only the intro FMV and not the game itself is actually possible to get working on modern systems - I hope not for OPs sake!

Or Dark Reign.

Oh yes! I seriously have to give that a go again. I couldn't get past the 2/3d level last time I played :P I still remember drooling over the intro vid they sometimes showed on Cybernet.

Actually since Rising Lands is fantasy themed I would also recommend another vastly underrated gem :
Majesty (the first one)

2/3d level!? I couldn't get past the fucking tutorial! :O

Lol I think the RTS genre went through a bit of a 'tough as nails' phase in the second half of the nineties : MAX (couldn't beat the first level), KKND(got hopelessly stuck on the 5th or so), Dark Reign, Majesty(ugh its awesome and everything but I've concluded that it is impossible to overcome the game). Proper old school games!

Yep, definitely an era of really tough RTS games. I've installed Dark Reign the other day, and had quite a challenge on the first few levels.