I think 3 things should be added:
1) More Terrain. Adds Tactics.
We need more "special" terrain. Currently we only have water and lava. We could have Hills that increase archer damage, and magic circles that add defence or attack. That way, fighting for certain positions on the map becomes more important.
2) More enemy types.
The pokemon catch them all part of the game is incredible important, but I guess that can also be used later on as DLC. Just here a few ideas: Aoe Healer, A fighter that is constantly confused and attacks friendlies too, A fighter that becomes invisible when exactly 3 spaces away.
3) More game modes in PvP.
My suggestions are Capture the Cupcake (flag), King of the hill, Siege (with a castle and everything).