Hi Martok
Not strictly fantasy, but have you tried Sid Meyer's Alpha Centurai. It is a SF Civilisation style game and an old favourite of mine. No magic but lots of discovery and mystery, teching up, empire building and the factions are all so different. Also there is a really good diplomacy side to the game. It runs on old machines and is now dirt cheap. Oh - and it looks beautiful with loads of screens when something has been achieved.
So if your definition of fantasy is not historic then give it a go.