I'm not sure about increasing difficulty through the reduction of cooldowns. If AI can't be improved (AI in this game is too abusable), I think the next best route would be to provide the creatures with abilities that the player has no access to. It'd be very hard to balance without getting insta-gibbed but it'd make for a very interesting game.
