My party was similar to Roccandil's, and it worked VERY well. Basically, pretty much any reasonable party will work in the late game, from what I understand, so actually a lot of the variance in parties is how they do at the beginning.
(I finished with the party I will describe on ironman hardcore.)
And mages are BY FAR the best in the early game. At lvl 5 or 6 They do 30 dam and hit every time, while any other char does around 8 damage and misses on avg around 1/4 of the time, which is plenty. One of the hardest things in the game is when you get attacked at low levels by hounds, like at lvl 5 you can get attacked by 2 young cursed hounds.
With 3 mages, you can crush hounds from lvl 3 onward, which is very satisfying. All other fights are not that bad, because you can mostly choose when to do them, between choosing which areas to explore and also with the camo skill (which I basically never use and don't put skill points in, but it is there if you need it).
You mostly only need to max 3 spells for your mages, plus it is very nice to have energy absorption. You can pick up some other spells that those 3, but once you know what the base is, it is easier to pick and choose others as you wish.
Those 3 spells are stone arrow (instead of sparks, the mis-named flame spell, heh), blizzard, and hammer of the destroyer (not meteor). By far the most common spell is Hammer. They key is wounds, not damage. Meteor does the same wounds but more damage for FAR more mana. Mages aren't really there to do damage after stone arrow becomes obsolete.
By focusing on Hammer, your mages actually don't run out of mana. Later in the game, they will be not as strong as your melee guys, but they will totally be fine.
Energy absorb helps give them something to do, and for some enemies that can cure wounds, it lets you drain them totally, like Earth Guardians and some Guardians of Yul and one or two of the titans.
Blizzard is great for some mid-game fights, such as most cursed hound fights, and fights against Khornil's elite guards that you don't need to fight, but that give you tons of experience and gold if you do (and with mages, you can).
You can put 1 point into mass lightning, normal lightning, frostball, a couple of points into brittle armor, but none of that matters too much.
Then I had Gaulen on the left, Barbarian in the middle, Thief with sword on right. Axe for Gaulen, Mace then hammer then Flail for Barb, short sword then claymore then katana at the very end for Thief.
Max learning immediately, nearly max shurikens, keep lockpick and traps at about 3/4 level, do perception with one mage and item identification with another mage. Around when you finish learning, build up immunity. Give mages some armor skill, enough to use light heavy armor (don't ask), a second point in daggers for initiative daggers.
Max herbology and dont pick herbs until then, of course. Ignore exploration. Eventually I took a point of hunting because I found 2 skill books, but you don't need it. Put a few points into envenomed and quick strike, ignore aimed strike. Max those when you are able, but no rush. Max rage after you finish with learning, take some tactics and weapons master but you don't need to try to maximize. I maxed meditation from early on for mages, which was probably correct.
Mages, always and only take con and speed. Melees, always speed, and maybe about half and half agility and str, using your judgement (such as if you want Gaulen to qualify for a big axe, he needs more str, whereas Flails for the barb take a balance with slightly more agility).
Of course, you can do something totally different and make a totally different party, but at least this gives you a sense of something that definitely works from start to finish and is quite fun and satisfying.
Oh, I should have explained, at a certain point, a particular enemy hits a threshold of wounds where it can no longer ever hit you. Before that, it goes through a period where it mostly misses and if it hits, does less dam. Plus it also gets hit easier, and then it hit automatically. With this party, you can get to that wound threshold very reliably. And yet if you hit an enemy that you need to bleed out, you have your thief. And having your barb to stun works great for controlling the pace of various enemies.
This party has great power just when you most need it, around lvl 5 and 6. It is very strong through the 20's and lets you fight both optional hordes of human guards. And it has versatility always. And you will be totally fine with no cleric. Just don't sell your lizard eggs...