Caveat (my opinion): Many of these recommendations are because these are the best builds for those sets, rather than the best gear for those builds. In most cases, runewords/uniques are better for each build, but it's nice to get some use out of the sets. You can of course complete the game with a naked character, so don't assume you absolutely have to use these build recommendations for the sets, do whatever is most fun for you!
M'avina's Battle Hymn: M'avina's complements Freezing Arrow well due to the +20% To Cold Skill Damage (Complete Set) from the gloves. Plus, the set isn't particularly geared towards physical damage builds, but you can still Strafe pretty well with it. Most people go for a hybrid with Immolation Arrow because FA and IA need the same type of other gear. It's just a shame that Immolation arrow is hampered by the cooldown timer.
For an Ice Maiden/Magezon, the Ice Runeword bow is much better than the +20% CSD from the gloves, but since you don't have high end runewords, this set is pretty good.
Natalya's Odium: The set isn't the best gear for a Phoenix Striker, but Phoenix Striker is a good (perhaps the best?) build for the set. A more physical build will want more crushing blow from boots and helm slot but those are already taken up by the set, so the set is not a great fit for physical builds.
Immortal King: Whirlwind...'nuff said...oh you wanted more...okay...Concentrate is too slow/boring. Can't Double Swing/Frenzy/Throw with this set, Leap Attack is a novelty build (I'm making one but it is hard work) and that leaves Berserk. Whirlwind is just quicker.
Aldur's Watchtower: This set really sucks. No FCR and minimal + Skills means that any type of caster is out and there are way better options for pure Summoners. This leaves melee, but the weapon is very poor - being Exceptional(ly bad) rather than Elite, so you want to augment your physical attacks with an element - hence Fire Claws.
Trang-Oul's Avatar: The set bonus of -25% To Enemy Poison Resistance (3 Items) from the head and the inherent +25% Poison Skill Damage from the gloves mean you'll definitely want to be a Venomancer for this build.
Griswold's Legacy: Lots of sockets to customise your build, the weapon is rather good and complements Vengeance well. The straight Adds Damage set bonii work well with Vengeance and Jewels can ramp the minimum damage up quite a bit.
Another option is the Abbot build, fill the set with Sol runes for lots of Damage Reduction.
Tal Rasha's Wrappings: This set can work with multiple builds, however, if you go Cold, you'll probably want to use Death's Fathom and Nightwing's Veil. If you go Lightning, you'll want to use Griffon's Eye. Fire on the other hand, doesn't have any great caster items (plus we're avoiding high end runewords). Therefore, it makes sense to go with a Fire hybrid build to make the most out of the set.