Mages have gear for movement speed.
http://www.ffxiah.com/item/15322/heralds-gaiters
and
http://www.ffxiah.com/item/14166/desert-boots
I realize the first one was mentioned in the OP as hard to get... but I mean a lot of times /sch is the best choice for a mage... so Sandstorm+Desert Boots will work well for many a mage... its like, 2 seconds to cast the spell in question to activate them.
Still i would like to mention the SAM/NIN boots, giving movement speed to SAM easily... Crimson for RDM and many a heavy armor job... but both the SAM/NIN and Crimson were as hard to obtain as Heralds at one point in time... (much more shortly so for the SAM/NIN ones lol)
So I think the only problem with Heralds is that they haven't become easier to obtain like the other non-Light armor options have... so maybe that would be good enough, making them easier to obtain? Obviously not super easy...