I think movement speed should possibly be a little slower, but mainly the map needs to be stretched out or redone. Everything is so close.
With everything so close to each other it could easily end up in a situation where pretty much all strat battles are siege battles. Now siege battles are pretty cool, and are gonna rule with cats and towers, but doing siege after siege is just draining. If the map was a bit more open we could have the chance for some field battles and it would make launching an attack a serious thing involving a lot of planning and timing of armies. Right now you can just skip over to your other villages and reinforce stuff super fast.
I'm thinking move speed should be determined by total weight of gear in the army. This could create a really interesting dynamic where you could have faster moving lightly equipped armies, but if they get pinned up by coordinated heavy gear armies they get smashed up. It could also have people moving lots of troops around as fast reinforcements but little gear so if they get caught before their destination they are in trouble. Just to add a risk/reward kind of thing.
Also maybe there could be an exponentially increasing move penalty for armies over a specific size? Right now the most effective thing to do is ball up every single troop your faction has into one army and have it go steamrolling.