S1. Anub´Rhekan was pretty easy imho. And it was the boss most of the guild went first to. S2. Grand Widow had a higher difficulty then anub but was still manageable. S3. Maexxna was still one of the easier wingbosses but you needed good dps and fast switches on the webbed players.
Overall i would say the difficulty of that Wing was still pretty easy and was more or less an entry wing.
P1. Noth was a fight where switching on adds was pretty important. Pretty much tank and spank with a little bit of adds. P2. Heigan was just about the dancing. Back in the days i can remember that failing the dance will result in a death. You could kill the boss easily with 20 men dying. P3. Loatheb was the first hard boss and most guilds went to him later and cleared Razu/Gothic/Patchwerk/Grobbulus/Gluth first. As a DPS you had to get leech/heal trinkets to stay alive. The darkmooncard that healed you was pretty strong and also getting leech/crusader enchants. Coordination was key.
So Plaguewing took you about 2-3 days of progress with 80% going into Loatheb.
A1. Patchwerk was a pain in the ass. The extra hits loved to bug out and kill your melees. Your healer need to preheal the tanks or they would die and they needed to focus on that for 5-10 minutes. For dps it was just maximizing like Butcher now. 1-2 days of progress. A2. Grobbulus was a joke 1-2 trys and he was dead. The blob gauntlet before the boss was harder. A3. Gluth was about coordination but overall still pretty ok. 1-2 days of progress and easier then Loatheb. A4. Thaddius was one of the most nerve wrecking bosses because in a 40 man wipe 2-3 people could wipe the whole raid. Enragetimer was pretty tight. Took you around 2-3 Raiddays of progress.
Overall Abomination wing had pretty insane and really cool fights (tight enrage) considering that most of the fights before naxx were just mostly tank and spank. 1-2 weeks of progress.
DK1. Instructor Razu was for me one of the most hated fights because you couldnt do anything to help progress him if you werent the one mind controlling the adds to tank the boss. So you just had to have good priests and hope for the best. Still just and entry boss for that wing so not much time was wasted. DK2. Gothik was about balancing your DPS and burning Gothik down in his last phase. Took 2-3 Days of progress to figure out the right combination of DPS on both sides. DK3. Four hoursmen was kind of like Thok (because you needed a certain amount of a certain spec and it was nearly impossible if you lack them). If i recall correctly you needed 8 Tanks and you had to have the 4 set bonus which would negate the miss chance on taunt on all of them. So most guilds had to reequip their warriors or rent warriors from guilds that had no chance to kill that boss anyways. Most of the guild wiped 1 week on that boss. But Ashbringer was a pretty nice price for killing him :)
Overall the Deathknight wing was the hardest one compared to the other 3 wings. The order of difficulty should be Maexxna < Loatheb < Thaddius < 4 Horsemen
The last wing (Frostwyrm Lair) 1. Sapphiron was impossible if you hadnt enough frost resistance. So you needed to either farm a shit ton of frozen runes or you had to bribe lower guilds on your server to sell them to you. Without that gear sapphiron was the end of your progress.