Sergeant Curtius in Cyseal's Harbor Warehouse sells legendary stuff in 50% of the loads. And he's available from the very start of the game.
Also the three Elementals in the forge (Hiberheim North) in the short period between destroying the Staff and freeing the White Witch.