I think one interesting way to add a little variety to the game is allow for more dynamic settings, for example:
Board Size - allow a range of board sizes
AI - there's something to be said for scaling AI, but perhaps you can also set it to something within a given range
Unit Types - I hear a lot of people complaining about different units being far too effective etc... like assassins, personally I don't see a problem with them... But rather than hearing these people complain, you could put in settings to allow/disallow certain units...
AI Start Locations - in coop, the AI really is pretty easy no matter what difficulty, as long as your both pick something that works well together giving the AI more starting locations would allow them more spawning points, which would actually make the game more difficult. Rather than selecting how many 'castles' they get, you could select how many 'deployment spaces' they get.
Templates - the ability to turn on/off certain or all templates
There are probably other settings that could be made more dynamic to allow the players some control over how they want to play, etc... Regardless, its something to think about...
time for 1 turn (form 1 to 3 min? even more for 2vs2?
Larger board option would be a cool variety. Mainly with two players using one castle it gets crowded and you don't have much time to setup. For me it's not a high priority though.
I disagree with letting players choose to ban units. Tweaking the more powerful units by, including cost, would be the better option. And is only needed if a unit is so strong that no other strategy can overcome it, which I don't think is the case.
re: Tek777, I think short turn times are very good because they test the skill of players to make difficult decisions really quickly.
This also makes games take less time, whereas with a 3 minute turn that would mean you would have many games last over an hour long.