Most of what I remembr is from IWD2 but your best bet with lower numbers of players in a party is to abuse some mechanics.

Specifically things like level 1 clerics being able to use all scrolls

Other things like taking Sorcerors over Wizard/Mage if possible also gives a large advantage.

Honestly, with a little bit of planning, a 4 player party should easily be successful. The game heavily favours melee combat, and any party that excels at melee will be successful. I'd recommend a thief/fighter, fighter, paladin, cleric.

You only need detect traps and pick locks from the thief skill set, so taking your thief to level 5 or 6, then dual classing to a fighter should yield good results, though you will spend a short time with out any thief abilities, so get scrolls and stuff. I like paladin's as party leaders and extra healing, but feel free to insert your favorite melee character, even another fighter is good. For some extra poopsocking, start your cleric as a fighter, get to level 5, then dual class to cleric. Once that cleric hits level 6, they are going to have access to weapon specialization, plus the added hit points will keep them alive during tough fights. Puts you at a small disadvantage early game with no healing (paladin!) though.

I know this sounds really basic, but you will smash through the early game, and the extra XP gains from having only 4 characters will help keep your party ahead of the curve. I like playing with wizards and crap too, but in Icewind Dale, they are more often a liability than an asset.

EDIT: I just remembered the thing wizards are handy for, finishing off trolls (burning hands). If you are going wizardless, stock up on fire arrows, burning oil, and any magic flaming weapons you can get, so you can kill the buggers. Otherwise you'll only be able to finish them off with a critical hit, which would be aggravating.

I soloed the game through to Dorn's Deep using a dual-classed human fighter-mage on hardest difficulty. Raising the difficulty doubles all experience, and quite frankly the monsters aren't that bad. You take some pretty heavy damage from some traps, but then just rest and heal no problems. Character stats were S 18/91, D 18, C 18, I 17, W 3, Ch 3.

Just finishing all quests available in Easthaven should raise you to 5th level fighter (that's even before going to the orc cave). By the time I made it to Kahlahar, I was 6th lvl and ready to dual into mage. Just clearing the start screen of Shadow Vale and the 3 smallish tombs, with a little bit of grinding Lesser Shadows and I hit 7th level mage and got all the fighter skills back before even setting a foot into the main tomb on this map.

I had some problems against undead because I had specialized in sword and bow mastery, so all my damage was halved. But Aganezers Scorcher combined with Web works like a charm for clearing large packs of undead, till you get Fireball later in the game.

About halfway through Dragons Eye, I realized I was leveling up faster than I could find spells to fill the higher level slots. You don't find any lvl 6 mage spells till Shattered Hand, nor lvl 7 or higher till Lower Dorn's Deep. So a solo mage is sort of a waste of experience in that sense. I was gaining levels, but wasn't getting any benefits from it.

In retrospect, I would start this particular game with a fighter/cleric either duoed or multi, I don't think it matters much. Only because most early enemies are undead and the cleric is made for that type of fighting. Clerics know all spells automatically once they level up, so no problems with empty spell slots. Just cast Sanctuary on yourself, you can walk around in full view of monsters and either passively-smite them (turn undead) or loot the treasure chests, then go back and kill whatever monsters remain with the powerful new weapons you found. Then I would bring in a fighter/mage character as you start Dragons Eye so as to have enough fire-based spells vs Trolls and Spiders. You should be able to complete the game with just those two characters (I'm currently testing this theory out). Halfway through Dorns Deep, each character hits lvl 20+ easily.