I think that the adjectival and, by extension, the adverbial form of legacy should be legatial and legatially respectively. This choice is based off the establishment of existential, gladiatorial, etc.
Words ending in the -ial suffix
The -ial suffix is a very simple suffix of converting nouns into adjectives.
However, many words ending acy tend to change -cy to -te:
Others change to -tic, because -cracy, meaning rule, is the suffix in these words:
Finally, there are a few that add the -ious suffix:
Finally, there is one that has, from what I can tell, no direct adjectival form (conspiracy) but whose closest adjective is conspiratorial, which comes more directly from conspirator. OED2 does have conspiratious (def: Addicted to conspiring) and conspirative (def: Engaged in, involving, or characterized by conspiracy).
Now, that leaves legate, legacious, and legative, excluding legatial. Legate already exists as a noun with a different meaning, although it could be used as an adjective. Legative, too, exists as a an adjective derived from the previous legate. Legacious has no precedence as a word and could very well be coined for such an instance, and the -ly suffix can be easily slapped on to make legaciously.