I remember a turn based strategy game that I used to play on an Apple II e. Erfworld basically reminds me of this game; there was a huge world map with different terrains for the units to cross (I do not remember if the game map was hex or square overlayed.) Cities all had different troops they could "pop," - and certain more powerful units took longer to "pop" than others. Also, it was fantasy themed, there were magic items you could give to your heros that would give them advantages in combat. (If I recall correctly, heros "popped" randomly, or you found them - not really sure.)
I would dearly love to find this game and play it again on some emulator, there is just one problem. I don't remember the name of the game. Does my description ring a bell with anyone? Does anyone recall this game and know the name?
Sounds like 'Warlords' to me...