Regarding hex-maps:
Now that I think about it, there is an alternative.
We can take a cue from Master of Magic. In that game, the battles were coducted on a Cartesian grid. But, units were chaged 1.5 movement points for going diagonally, which is a fair approximation of reality (the actual distance is 1.414). And units were not allowed to move at all if they have 0.5 movement points remaining.
People may now debate whether or not a unit with a fractional movement point should have it added to their movement points for the next round or turn.
--Raynfala