I had an idea about salvaging the uber-strength animals, in an attempt to keep the 'world's a dangerous place feel' and maybe bring back some of what Kael's talking about in
this thread. Specifically:
Wilderness Areas: Areas that have to be conquered before they are available to settlement. You may need to clear out the monsters, defeat a boss monster, or whatever. They should be formed by natural borders (such as rivers, mountain ranges and forests) and we would have a few different types with different properties. Some may require units to be a certain level before they can enter them. This idea became explorable lairs, which is a much more realistic vision of it. Though I still dream about the origional idea (i know a lot of the team really liked it).
What about, instead of having the powerful creatures free to rampage around the map as they please, you turn their lairs into cultural zones like forts, and the powerful creatures are only able to move around in their cultural zones/territory? Weaker units, under the guise of having to "go out to find territory" would be the only ones free to leave the borders. If a weak animal unit somehow survives long enough, maybe to the point of becoming a beast (or later still if balance requires it), the unit forms a lair and a new territory region for that creature is spawned.
Inside these territory regions would roam either packs or strong (e.g. the currently bugged out strength, maybe a little weaker) single units to simulate these areas being extremely savage and requiring an organized effort to clear and make safe. These territory regions should also take precedence over your cultural borders, showing that it takes an organized effort to make the region safe (and to prevent potential bugs like creatures getting pushed into your territory, then free to run about as they please, when they should not be able to). Owing to this, lairs should probably not spawn for the first couple of turns, and they should not spawn within several tiles of cultural borders either, though the intent is to make it feel like these lairs and regions have been around for centuries, before civilizations begin to re-emerge.
This might also be applied to barb units, although I guess cities work fine there. (On the flip side, if barbs only use forts, you can allow players to populate the fort after conquering it, turning it into a city, maybe with some initial defensive buildings.) In this case, though the barb population is very dense in their "cultural" radius or territory (simulating a very barbaric region that needs to be pacified), they send out raiding parties whose strength is based on the world's tech level. Depending on how much lag it induces the units inside the territory should fight themselves and (very) slowly gain in strength, as you'd imagine barbarians would do when they're not out raiding. The raiding parties would be independent and would be more akin to the current flavor of barbs who venture out and invade your territory.
This allows you to keep some of the stronger units around, like minotaur and hill giants (or sabertooth tigers or giant scorpions), but they are limited to their territories. Weaker units would be pushed out, the ones who need to establish their own territory, and they are the ones you need to defend against.
From what little I know of such things, I suspect it would be difficult to use map-generated features (like mountains and rivers, as Kael mentions) to limit territories, but that would be a neat addition if it is possible.