I don't feel that we have a problem to fix. The movement rules
for ships on coasts means they can often move very cheaply in
a sort of pseudo-diagonal way. There exist diagonal routes in
the square grid now (hidden routes). I think the system of movement
point costs we have now is very well done, and I don't see a need
to change it.
Another thing that makes it better is the fine granularity of the map,
and the way a unit can move many squares in a month. If we could only
move a couple of provinces a turn I'd be calling for diagonal movement
too, but I really don't think we need it.
Diagonal movement means it's harder to guard against someone, or to
fence someone in (6 neighbouring provinces instead of 4). This would
mean reconsidering noble and army costs, perhaps. It would complicate
the Great Castle Debate, too!
-- Chris Yearsley email@example.com