Personally I would recommend against Lord Arn's recommended party. You have no pure mages or clerics in the bunch (while the healing duties will be ok with a multi classed cleric and a multiclassed druid in the group you still miss on high level cleric spells). But then there is mage. You have no pure mage. Multiclassed characters do not level up fast enough and for mages that means you miss out on the best spells (you will not get to cast level 8 mage spells with aerie by the end of the game).
Personally I think from a pure power perspective Anomen is the strongest NPC in the game so don't bail on him unless you really need to.
I agree on not using yoshi. aside from the afore mentioned reason Jan (along with minsc) is the most entertaining NPC in the game. he is great at all non combat thieving stuff and is good as a backup spellcaster. Also there are some classic interactions with Jan and some of the other NPCS (hehe I still laugh when I think of Jan's story about the flesh golem
Actually if you do what you said and replaced mazzy with keldorn (the paladin you refered too) and ditched yoshi for Jan that would be similar to a party I had gone through with once before. very melee heavy. works great