It would be appropriate for a BM-like game to be called "Age of ____" considering the map graphics used are likely to be from Age of Wonders. It also sounds very pleasant.
I don't like the "Legacy of ____" names, because they make me think of something more fantasy oriented like Warhammer, where there's wizards and whatnot running around lusting for blood and power.
"____ of the Sword" names aren't good, because they sound like book names. They make me think of the tale of Excalibur, not so much of a sandbox MMO game with no general plotline.