Majesty.
It wasn't actually a sim, and it wasn't your average RTS strategy game, and I think that confused a lot of people, including the marketing folks. It had this premise of being a RTS but you couldn't actually control your units/tell them what to do or where to go via mouse clicks...once you 'get that', it's a ball to play...plus all the unit types had mini-personalities, and loyalty factors (rogues could be enticed to an enemy player in MP with enough gold) and certain races had certain bonuses to you the King etc.
I don't typically like RTS games much, but I played Majesty for a long long time.
Edit - the Northern Expansion had some maps that were a serious challenge even for experienced players...great stuff.