By my experience, unless you use danger rooms, legendary warriors can be potentially years in the making. Most maps have wildlife, and the caverns always have some nasty, yet relatively weak, denizens, and all can be targets for a sort of field training. Also, I find that even low-skill recruits, when decked out in a full set of steel armor and equipped with a steel weapon, can pretty well handle an ambush squad or two. A lot of my military hangs out at Adequate or Skilled fighting abilities for a long time, but if they've got enough good equipment, they only suffer maybe one or two minor injuries during ambushes. Sieges aren't for the weak, but you generally don't see those until your military has been around for a good while.
Also, I'd like to add that smaller squads with low minimum training requirements seem to do better with training. Correct me if I'm wrong, but when you have a squad of 10 with an 8 minimum training, they won't do all that much unless a total of 8 dwarves are ready, i.e. not eating, drinking, sleeping, being obnoxious. This can cause problems, as if one of those 8 gets hungry or decides he's tired, the rest are kind of loafing until at least 8 are ready... by the time that happens, one of the other ones gets thirsty, and now you're waiting longer, until another gets hungry... you see how that's going. Setting your minimums lower might help with getting more going on in the barracks.