For a first time Icewind Dale player

I'd recommend a 6 character party, or maybe 5, depending on how comfortable you are with the ruleset.

1) Human Paladin - see below
2) Dwarf FTR - pump his CON as high as possible, give him 18/91+ STR (preferably 18/00) and decent DEX. He's your other tank.
3) Elf FTR/Thief (see below)
4) Gnome CLC/Illuionist
5) Human mage
6) Druid or Bard

If you're good with the IE games and the AD&D ruleset, I might try something like this:

1) Human Paladin - your primary tank and your party 'face'. Try to get 18/00 STR if you're patient enough to keep rolling, 18/91 or higher if you don't want to spend a lot of time on rerolls. 16+ CON, minimum WIS (13 for a Pally, I believe), high DEX if you can. Put points in Large Swords, as the best weapon in the game is a longsword only useable by Paladins.

2) Human FTR - dual class to Druid after reaching level 3 FTR. Again, high STR, high DEX and 16 CON. You need 18 WIS and 17 CHA as well. Tough to roll this one, but well worth it. Druid spells rock. Put 3 points into Scimitar (large swords).

3) Human RGR - dual class to Cleric after reaching level 3 RNR. High STR, DEX, 16 CON and 18 WIS. Use a two-hander for this guy. With no shield equipped, you'll get an extra attack per round - alternately, you could spec him in hammers, as there are some nice ones in the game.

4) Elf FTR/Thief - Give him 19 DEX and use as a ranged attacker with a bow.

5) Human mage - generalist mage, so you can learn all spells. 18 INT. (If you're comfortable trying to start off without magic riht away, I'd actually go for 3 levels of FTR, then dual to mage. This gives you the ability to use a longbow so you can use this character as a second ranged attacker at need and also gives you more HPs to deal with).

6) 1/2 Elf Bard or Human specialist mage. 18 INT. If you decide to go with either of these, you can specialize your first mage for the extra spell per level. Split your scrolls between the two and use one for AoE spells and disablers and the other for attack spells. You can use the Bard for your party 'face' if you want as well. And with an 18 INT and 15+ CHA, you're set for all convo options.

I played the game many years ago, and picked it up here when it appeared on sale, as my discs have long since disappeared. For my first run through since buying it here, I went with a 3 character party:

1) Human FTR dualled to Druid at level 3
2) Human RGR dualled to Cleric at level 3
3) Elf Thief/Mage

This party levelled fast, due to only 3 characters, and they rocked. Very effective, and I had all the necessary bases covered with just the three of them.

I consider the following party the best (recommend weapon profs and minimum stats (str-dex-con-int-wis-cha))

1) human fighter3/druid dualclass (+++ sling, ++ sword) 18/..-18-18-3-17-17
2) human cleric5or9/illusionist dualclass (sling, mace, hammer, flail) 14+-18-16-18-15+-3
3) human ranger7/cleric dualclass (++ sling, ++ mace, ++ flail) 18/00-18-18-3-18-3
4) half-elf bard (bow, halberd, greatsword, crossbow) 14+-18-16-18-3-15+
5) dwarf fighter/thief (++ bow, ++ dagger, ++ long sword) 18/00-17-19-useless
6) gnome axe fighter (good aligned, +++++ axes, ++ bows) 18/00-18-18-useless

My approach is quite down to earth: get a couple of tanks, then make sure everybody else can use a bow and you'll mow down the world. And if a couple of them can cast Web and Fireball too (create a human fighter, when he's level 2 dual to mage) consider the credits rolling by the time you finish with the character creation.

This is my party now in insane difficulty:

Fighter/Thief - simply the best archer (bow, sword)
Cleric/Ranger - tons of really useful spells and good fighter and good AC (any armor can be used) (sling, mace/flail)
Fighter/Druid - really good spells and good fighter and good AC (any armor can be used) (sling, scimitar)
Fighter/Illusionist - tons of spells and the second best archer (bow, sword)
Bard - spells and lore (very, very, very useful for identification!) also very quick level progression (crossbow, sword)

First what you want to do is to make sure everyone in your party has ranged attack (bows for fighters & thieves, slings for clerics and druids, crossbow for the bard). That's you first line of defence! Yeah, if the enemy cannot hit you coz you kill them before reaching you, you already won.
Second, you need to use tons of spells, especially area spells like sleep, blur, entangle, web, spike growth and the usual fireball and the like. You will need lots of fire/acid based attack (either with magic weapons or spells) due to the large number of trolls you will encounter.

Ohh, and if you play just on normal difficulty, don't use a lot of multiclass characters since your level progression will be somewhat slow (the fighter/thief can be an exception).

So a good party for a starter could be:
Fighter/Thief - you need thief for the traps (bow and sword)
Cleric - you'll need tons of healing (sling and mace/flail or hammer)
Druid - really good spells and can use scimitars (sling and scimitar or spear)
Illusionist or other specialist - moar spells (sling)
Bard - spells and lore (crossbow)
pick any for the 6th, a Ranger, Paladin or simply a Fighter could be a good choice for a tank. But if you use only 5 characters, your level progression will be faster. Btw, I like Druid and Ranger since they have healing spells, Sunscorch, Entangle and Spike Growth, simply just great spells!

Ohh, and you need one character with high charisma (Paladin or Druid is perfect for this), and make sure he/she is the first in your party when entering shops and talking to the shopkeeper since you get discount for high charisma.

Btw, don't play on easy since you'll get less XP and loot. The higher the difficulty the more XP, loot (especially magical stuff) you get! Also you'll need more time to plan your battles which makes the gameplay somewhat tactical. Turning on the auto pause options help a lot!

You get the same XP bonus (+50 percent) at easy difficulty as on hard, and the same at the easiest (+100 percent) as on the hardest.
There are only a few extra monsters on harder difficulty to fight, not enough to change XP or loot significantly.

For talking bards are even better than paladins or druids. They get a few bard specific extra options, their 15 cha minimum grants all charisma based options and they can raise it by 5 with the spell for optimal shop prices.

Well this is the 4th time I'm playing through the game and I can tell you that I get much more magical loot on insane difficulty than on easy or normal. And it's not related to the number of the monsters, the most magical stuff comes from the chests and shelves (the same chests give better loot if you turn up the difficulty).

Loot from containers like chests and shelves doesn't change when you change the difficulty. Some of the loot is random so having better luck at your harder difficulty games might have caused your wrong assumption. (mods or installing the expansions also change loot)

I've played through the game (including both expansions) 5 times and I can confirm that loot doesn't even change in HoF mode.
If you don't believe me you can search for Dan Simpson's IWD FAQ/walkthrough (available at gamefaqs for example) who describes exactly what items you can find where or use a program like infinity explorer to look into the game mechanics yourself.

Some miscellaneous tips:

--Ranged weapons are key. Every character must have one, especially if you have a low number of characters (1 to 3). It's also very useful if one of your warriors gets mortally damaged, just exchange his shield for his crossbow, put him in back, and keep on attacking.

--IWD is very similar to Starcraft in that the arrangement of your units (characters + summons) is KEY to winning battles. Put your thief in back with her bow next to your mage, put your paladin and fighter in front. If you mess this up, if there is even the most minor of traffic jams, people will die. For this reason I recommend avoiding the standard formations and just giving each character a specific movement order in any dangerous place.

--Don't roll for stats. Just use Dalekeeper (google it) to get the stats you want. The thing I loved about NWN was they got rid of the whole "roll" thing so if you wanted 18 strength, you just click on it! I never saw why clicking a button for 2 hours until the right number comes up was supposed to be "gameplay".

--Long swords are definitely the best weapon in the game. Unlike in NWN/BG2, greatswords in IWD suck (with the exception of a few bastard swords weirdly categorized as "greatswords"). There are a lot of good long swords available, enough for 3 warrior characters. There are a couple cool shortswords too.

--- You will meet a good character named "Marchon of Waterdeep". Even if you are not evil, kill him as soon as you meet him, preferably by locking him in his little room so he can't run away. This is because he has the ONLY (the only) long sword in the game with 100% guaranteed fire damage (unless you want to shell out $32,000 for that shitty sword that Conlan sells in Kuldahar). It makes killing trolls and Revenants a lot simpler in the long run.

4 Person Party = 50% more exp if you want to try it. The party below will cover all your bases and you'll have a wad of magic to pick from. I would recommend making sure you have characters of a variety of alignments as certain equipment doesn't work on Alignment X. Plus your whole party can wear plate except your Bard who can wear Chain mail. Your bottom two of course can't cast while they are wearing armor - but its nice to be able to toss it on in a pinch, most of the time you'll use them for great archers. Use the suggested scripts if you want to have full control of your spellcasting.

Half Elf Fighter/Druid - Scimitar, Dagger, Sling optional, Fighter Aggressive Script
Gnome Cleric/Thief - Mace, Club, Flail, Sling optional - be sure to take Mace early as you get +1 maces like crazy early on, Fighter Passive
Half Elf Bard - Crossbow - you get a +5 Thac0 crossbow early, Axe, FIghter Ranged
Gnome Fighter/Illusionist - Bow, Sword (you could flip flop Sword/Axe between the Bard and F/I if you prefer), Fighter Ranged

Gnomes have great saving throws against spell which is the most common. Half Elves are better than Humans when you're not Dual classing, you get a bit better saves... if you prefer you could dual Fighter -> Druid at Fighter 3 but I'd sooner take the extra THAC0 throughout the game.
Try putting Grease (Mage L1), Entangle (D1) and Web (M2) on a choke point, then overlaying with Cloudburst (D3) and Spike Growth (D3) for dirty AoE DoT. You can add further trap spells to that combo such as Glyph of Warding (C3) or Skull Trap (M3). Then drop whatever AoE spells on top too such as Fireball.

Bump, since I found this useful.

I myself found extreme utility with my final, and preferable, as of still now party; 3 playable characters only. A Chaotic Neutral Fighter Thief Multiclass Elf, large swords/bows, 18/00 str, 19 dex, 17 con, 10 int, 4 wis, 10 cha (lucky roll this one). A Chaotic Good Cleric Ranger Multiclass Half-Elf, 18/00 str, 18dex, 18con, 4int, 18wis, 3cha (lucky roll although barely made it into 18 to all stats of interest). And a Chaotic Evil Cleric Mage Multiclass Half-Elf, 10str, 18dex, 16con, 18int, 18wis, 3cha (good roll too, but spent lots of time to get it, as for the other 2 ones).

With this combo, you will be a powerhouse. Let the Fighter Thief wear heavy armor (detect traps is still usuable), while having a st.leather one to change into when thieving is involved. The cleric mage, thanks to being evil, will get priest offensive spells (like poison, cloud of pestilence, slay living, the causes of wounds etc.), perfectly augmenting his already damaging, wizard ones. And thanks to wearing robes, you can still equip that ring of protection +2, which you pickpocket from the potion seller, in airship, in Kuldahar. Finally, the Ranger Cleric is a powerhouse of his own, learning both cleric and druid spells, except for the 7 level druid ones (you do not really need them). Because he is good, he is going to learn the cleric good alignment exclusive spells, also, but make certain none of your clerics are lawful (1 or more spells are unobtainable to lawfools). This combo, evil cleric mage and good cleric ranger, will give you the entire lists of wizard, cleric and druid spells, in just 2 characters, and taking care to raise their main stats in initial roll appropriately, you will have numerous, happy slots to cast! Also, since the fighter thief is elf, he gets racial resistances and bonus to bows/large swords, and large swords can be used for thief skills like backstab. The others are half-elves, so they get limited resistances too, which is also great. And do not worry for cleric mage's low strength score, when he starts raising serious level ups, the cleric divine strength buff which raises all his physical attributes by 1 point for every 3 levels, will work wonders on him.

My formula has been 3 melee(paladin/barbarian/fighter/ranger), 1 thief, 1 mage, 1 cleric in IWD. I haven't tried a <6 party, but you should have no trouble running this lineup, especially when equipping everyone with ranged weapons.

Ever since I got this game back at 2002, this was the party structure I've mostly stuck with (which was always a 6 man team)

1. Human Paladin. I'm not 100% sure why, even though a Paladin isn't as proficient with melee weapons as a pure fighter I've always felt more comfortable with a Holy warrior leading a party against the forces of evil. That and he is the only one who can use the "Pale Justice" long sword (which is one o the most powerful weapons in the game, if not the most powerful IMHO). His weapons of choice was always a Sword/Shield combo.

2. Dwarven Fighter. It's always a good idea to have a couple of tank fighters, one of them being a Dwarven fighter (due to their high constitution) even though their defense will lack slightly (no thanks to the penalty to dexterity). His weapon of choice would be a sword/shield combo.

3. Usually a Human fighter. I've always saved this slot to experiment with different characters using different builds. I once tried a Human Cleric, but was dissatisfied with his defensive & offensive capabilities. I also tried out a Halfling fighter, mainly for the helmet halflings could use. But most of the time I would pick a Human ranger. But rangers have limited capabilities in this game, so for the best offensive choice nowadays I'd pick a Human fighter that specializes in 2 handed weapons.

4. Human Cleric. A cleric is always a must in these D&D games, but one with the highest strength, wisdom, and constitution score possible since I'd make him join the fight with the others. Weapon of choice would be a 1 handed blunt weapon/shield combo.

5. There are *alot* of traps in this game so a thief character was always a must. And what better character would make a good thief than a Halfling thief? At first started him out as a human but later playthroughs I'd make him a Halfling. Weapon of choice is a short sword/buckler combo since I'd make him get into the fight with the others (yeah, I'm insane I know).

6. Elven Mage (which I'd do my best to make him look like a Drow). One of the things I like about this game over Baldur's Gate 2 is that there are alot of Offensive spells in Icewind Dale. Baldur's Gate 2 lacked alot of offensive spells but this game was packed with them, and a good many awesome ones (especially the new ones Heart of Winter would add). Weapon of choice would be a Sling (with a many enchanted bullets as possible).

Best is to solo the game with a cleric/mage multi-class. On hardest difficulty, you should come close to hitting the max level cap of 30/30 quite easily by the end. Real men use bracers and magic buffs :P