So you have just one huge flat world?
Generate random spawn point. Check Terrain at that point. Place the appropriate enemy there based on terrain and distance from the lair (I assume that's how you are handling difficulty, distance from lair).
What's better though is if some points would spawn an entire tribe, so you can fill an area with, say, 1 orc chief/boss, a shaman and a few of his goblin underlings (archers, warriors, etc...) running around in the perimeter of his domain. So that entire area becomes filled with green skins. Gives that section of the map a bit of flavor.
Towns should spawn city guards and what not. Some Naga's running around by the water, etc...
I have seen some games that seem to create enemies by reproduction. Like the game spawns leaders throughout the land, then the game runs a few turns as the leader produces random minions who run around doing stuff. Run 50 turns then turn off the breeding.
Just some ideas.