Let's look at the available types:
Aberration: Not really worth it most of the time - most of these are insane or irrevocably evil - and the cost of having a mind flayer or beholder is likely to outstrip its usefulness to the group. Choice pick: Mind flayer?
Animal: medium-priced, but not too dependable, and you will need somebody to direct them. Great as mounts and maybe small groups of druids, but that's about it. Choice picks: warbeast dire tiger! Baleen whale!
Construct: very expensive and requires a high level wizard to get them - I can see 1 or 2 high level constructs as the core of a fighting unit, but mostly they don't seem worth it. Still, high DR coupled with magic immunity is nice. Choice pick: Helmed Horror!
Dragon: also very expensive, but highly mobile, intelligent, durable, and damaging - and there are class features and spells to gain these as allies too. A pretty top recruit in my opinion, especially the good-aligned ones. Choice pick: Whites and wyverns are stupid enough to be cheap, while silvers are the most likely to help a good cause.
Elemental: Can be cost-effective to planar bind them or have a cleric rebuke them under control - I'd rate these between outsiders and undead personally. Choice picks: air elemental scouts, or water elementals in a sea battle!
Fey: Probably good as scouts and maybe you can bribe them with berries or something. I don't know - I'd die before my overlord hired a bunch of nixies personally. Choice picks: pixie scouts!
Giant: A classic member of Team Evil's armies. They're generally stupid, which makes them cheap, and can be very effective supplements to other units. Choice picks: hill giants probably have the maximum HD to stupid ratio, while wartrolls' listed cost is CHEAP for their effectiveness.
Humanoid: Cheap and affordable, and the fantasy standard assumption. For ease of hiring and cost these can be worth it in almost any fight, especially since they tend to be the most intelligent cheap buys. Pretty much every army will have at least a few of these. Choice picks: dwarves can rock pretty hard, and I love me some water orc barbarians.
Magical beast: Not much here really - unicorns or blink dogs might be nice...
Monstrous humanoid: These are some weirdos and unlikely to be found in large numbers, but they can help fill niche roles. Choice picks: maybe minotaurs or umber hulks?
Oozes: Um, no. Choice picks: gelatinous cube mounts!
Outsider: Great picks, but you'll need a mid-level spellcaster to get these and you can only bind/ally a few at a time, which makes them nice leaders and support. Can be expensive if using planar ally too, so these are really the top choices for rich kingdoms with powerful spellcasters. Choice picks: the planetar!
Plant type: for a druid, an army of shamblers and treants is pretty feasible and the best substitute for undead - for anyone else this is a pass. Very cheap too. Choice picks: I'm a fan of treants
Undead: medium cost and tireless, and need a low-mid level cleric. But they are generally evil and have severe alignment/creepiness issues. For Team Evil, they're a no-brainer and the backbone of an army - for good armies you're probably better off with something else. Shadows and wights can also create spawn, cheaply enlarging your forces.
Vermin: Unless you're being thematic, these aren't worth it in my book, except maybe a few scorpions that the high level druid turns into insectile ATATs.
Brief analysis: if you want to build an army on the cheap, you're looking at a mix of weak undead, humanoids, giants, and animals. If you're moderately wealthy, you'd probably want stronger undead and giants, and then possibly a dragon and a high level spellcaster on retain for items, constructs, or summoning. If you're fabulously rich or have cheap high level spellcasters, then constructs, outsiders, undead, and dragons are going to make up your army.
I really think that an E6 game would be a good testing ground for D&D 3.5 warfare, since it's the point where undead come on board as a cheap option, but the really crazy stuff is still unobtainable, and a spellcaster is still more useful as a support guy than anything.