This one ought to be easy to implement, yet highly effective:
A filter switch for replays, that skips the animation for 1-Turn and 2-Turn units, please!
I just watched a 25 turn replay on a large map, and it took, like, forever! From turn 1o onwards, I really just wanted to see where the heroes and the big stacks are marching. Most big stacks contain a hero (3-Turn) or another >= 3 Turn unit, so this ought to be quite effective to speed up the replay - or rather, even if skipping the animation does not save much time, it allows the person watching to focus on the important events...
...I am really sick of watching scouts move forth and back between cities adjacent to watchtowers...so..boring..