It's possible that there are other threads on this topic that I've missed, but I did a search for every term that I could think of (legendary legendaries feat). So...let me know if I missed something.
The basic idea here is that legendary dwarves should deserve the title. Did Paul Bunyan cut trees a bit faster than mortal woodcutters? Of course not. Why should the living legends that the dwarves have be any different?
I will go through the skills, one by one, and try to think of a not-explicitly-magical legendary feat that legendaary dwarves might be able to do. The legendary dwarf will be referred to as Morul McLegendary, after the legendary Morul, who became a legend for being legendary.
Given the new system, allowing Morul McLegendary a 75-90% chance of getting a stone would be neat. Another option would be to greatly accelerate the rate of mining for legendary miners, or (more cinematically) allow them to throw a pick at a stone wall and have it mined (maybe just one tile, maybe a short line) by the time the dwarf can get over there.
Maybe this is best handled by the current system of legendaries making a crapton of legendaries. If not, perhaps legendary carpenters could carve still-living trees into furniture. urist McLegendary would get a job from the carpenter's workshop, and if a live tree was closer than the nearest log, they would go to that tree and make a bed or bin or whatever out of it. Perhaps this would require a knife/sword/whatever.
Perhaps simply greatly accelerated speed, perhaps something like mentioned under Mining where Morul McLegendary could throw his/her axe at a tree and it gets cut down (along with other trees and unlucky goblins in its path).
See Carpentry. Urist McMorul might also get a bonus when shooting with his/her own creations.
Like Carpentry, Masonry could be feat-ed by simply keeping the current system, perhaps with an increased possibility of masterworks. Another possibility is to increase the speed at which they carry boulders, maybe allowing them to treat boulders as though they were in a wheelbarrow (rolling the boulder in front of them). I'm not really sure. Morul McLegendary probably shouldn't carve stuff out of stone walls--that would ruin fortress design.
I'm not sure. Life-like images? Being able to engrave on tiny stone crafts? Just increasing the number of masterworks?
Perhaps animals trained by Morul McLegendary will never revert to a wild state, and skip past the semi-wild stage of training. However, as
weenog pointed out, this would greatly reduce the ability to train a new animal trainer. Perhaps legendary animal trainers can remove the "Hostile" tag or whatever it is* from captured goblin mounts, and/or can train war and hunting animals without TRAINABLE.
*Not a creature token, the bit of code that says "This creature is an enemy of dwarves."
Morul McLegendary can calm down angry attackers without CAN_SPEAK or INTELLIGENT.
Maybe awesome hiding skills? The Ambusher skill is the hunting skill, after all. For legendary marksdwarves, see below.
Morul McLegendary could look at a dwarf and instantly diagnose anything wrong, from forgotten beast fevers to therianthropy (a semantic's way of saying "lycanthropy"). Very useful for finding vampires, and so probably their earler targets.
Any treatment applied to a dwarf by Morul McLegendary would halt/slow/stop/cure infection and/or accelerate natural healing for a time. That's about as close to healing hit point damage as DF gets.
Here come the farming skills...
No clue. Maybe they could butcher dead animals as fast as they currently do live ones? Combat skills might be increased, and the creature might completely lose tissue if attacked (Morul McLegendary slashes the Lasher in the right upper arm with his +steel short sword+ and the skin flies off in an arc! Morul McLegendary slashes the Lasher in the right upper arm with his +steel short sword+ and the muscle flies off in an arc! Morul McLegendary bites the Lasher in the nose, tearing apart the skin!).
I'm not sure. Tanning the skin of live creatures sounds neat, but would require the implementation of tanning chemicals and probably not be remotely healthy for the tannee.
Plants planted would act as if fertilised even if not. If fertilised, they could grow much larger, big enough to be cut apart for use in many meals or perhaps even to be used as wood.
Perhaps Morul McLegendary would emanate an aura of cleanliness for a few tiles (keep him AWAY from the farms!), or maybe the soap would just give extra happy thoughts from useage in baths (Urist McDirty enjoyed Morul McLegendary's soap recently).
Morul McLegendary would be able to get useable amounts of ash or charcoal by burning vermin remains or withered plants or whatever.
I'm not sure. These two seem connected, though.
Dwarves drinking Morul McLegendary drinks would get an extra happy thought (Urist McThirsty enjoyed Morul McLegendary's drinks recently).
Not sure. Maybe Morul McLegendary would pick as many plants per shrub as would be grown with fertiliser?
Morul McLegendary cheese would give happy thoughts when eaten (Urist McCheesy has enjoyed Morul McLegendary cheese recently).
Milk milked by the dwarf would give happy thoughts when drunk (Urist McDairyLover has enjoyed Morul McLegendary milk recently). The milk would also make better cheese.
Hair grows back faser after Morul McLegendary shears it?
No clue, unless thread ever gets quality.
Food cooked by Morul McLegendary would give happy thoughts when eaten (Urist McHungry has enjoyed Morul McLegendary's meals lately).
What's pressing even useful for?
Bees flock to Morul McLegendary. If s/he opens a hive, no matter where it is, the bees will start flying towards it in a huge cloud, scaring and perhaps stinging any dwarves in the way. (Hives underground would need to be taken care of by beekeepers, although not neccisarily the legendary one.) More interestingly, when under attack, Morul McLegendary could summon such a swarm if there were any nearby beehives, distracting and hurting enemies long enough to escape.
Phew...
Morul McLegendary could catch any creature submerged in water, even non-vermin ones. The creature would be immobilised for a bit, unable to move or attack, but it would be wise to summon the militia in case of cave crocodiles. Hopefully, the caught critters would mostly be things like carp, sturgeon, and sea monsters that airdrown. This could be useful for rescuing drowning dwarves, too.
See "Small Animal Dissection"
Having a legendary smith is usually reward enough itself. Maybe Morul McLegendary could smith without fuel or magma, but that would likely be OP.
[spoiler=Furnace Operation]
Morul McLegendary could generate enough heat with his fists and force of personality that he needs no fuel! Smelting might take longer, but with the legendary speed boost it'd still likely be swifter than using an untrained smelter.
Morul McLegendary could cut stone to glassy perfection! So...like now, except that cutting stones works less well for non-legendary dwarves.
Perhaps tweak the rate of legendaries?
If not, there's several possibilities. Some can take cues from similar non-craftsdwarf skills (like woodcrafters crafting directly from trees, or stonecrafters rolling boulders quickly), but others require their own ideas. For instance, weavers could create clothes that give periodic good thoughts (Urist McNotNaked was glad to be wearing Morul McLegendary's clothes recently). Bone carvers might carve the bones of the living, although that might not work well.
Morul McLegendary would have a wider arc of fire.
Engines made entirely out of parts made by Morul McLegendary would be able to...do something. Maybe it would increase the arc of fire. Naturally, this would be awesome when paired with a legendary siege operator.
Engines made partly out of Urist McMorul's parts would not get much in the way of bonus. Maybe non-masterwork parts would have an increase in quality for determining accuracy?
No clue. Maybe Morul McLegendary could "pump" water with a corkscrew and a pipe?
Buildings made by Morul McLegendary give happy thoughts when seen (Urist McEyes was pleased to see one of Morul McLegendary's buildings recently).
Morul McLegendary can dodge things that aren't normal attacks, like dragonfire, or a flood, or taxes.
Morul McLegendary could run all day in full plate.
Morul McLegendary could probably buy Urist McNormal's grandmother. More appropriate for gameplay, deals with traders would be improved, and/or Morul McLegendary could convince attackers to stop attacking (until attacked, at least). The probability is low that they would accept the offer, but multiple legendary bargaining skills would greatly improve chances.
I think it's more than Record Keeping...anyways, Morul McLegendary could do complex math in his/her head. Among other things, this would let the player see the trajectory of minecarts on current hauling paths and probably some other useful things as long as Morul McLegendary is conscious and not bedridden.
Morul McLegendary would raise the skill of other dwarves just by excersising it near other dwarves. This would be very useful for the militia.
Morul McLegendary would raise his skill just by other dwarves excersising it near him/her. This would also be pretty useful for the militia, at least that one dwarf, and a bunch of students could be trained for each teacher.
That should be about all of them!