Abao has a good build and I 100% agree the best thing in the game is to just go explore. Look to your minimap to see where you can go. Talk to NPCs and pay attention to what they say. NPCs can give lots of tips to completing quests.
Summary
-------------
Lohse/Ifan : Wayfarer/Summoner - Summoning focus with a bit of Geo and Huntsman
Fane : Spellcaster of some sort - Geo to get access to poison spells is nice, Pyro to watch the world burn - once on board Lady Vengeance max Thievery
Red Prince : Fighter - Warfare/Geo - get Pet Pal talent, this will be both amusing and quite useful
Sebille : Scoundrel/Polymorph - high dps, lots of fun and some good CC once you get to the Lady Vengeance
This is a highly versatile group that can take advantage of any weapon you come across.
In Depth
------------
My default party make up is an Archer/Summoner (can to physical or magical damage - magic damage is from summoning incarnate on appropriate surface and special arrows), a strength build tank (physical damage - someone to carry lots of crafting supplies), a spell caster of some type (magical damage) and a Shadowblade (physical damage and thievery). This is a solid set up as the Archer/Summoner allows you to go 3 physical damage characters and 1 magic damage when the encounter needs it or 2 physical damage and 2 magical damage if the encounter needs it. The tank and Shadowblade should be packing grenades in case they need to do some magical damage. Also, building up a magic school on the tank can give more magic options as well. Geomancy and/or Hydrosophist are good magic schools to add some CC to your tank and allow the tank some magic damage is the encounter needs it.
This setup is highly versatile and can take advantage of every weapon you come across giving you even more options to handle encounters. More options is good for new players not yet familiar with game.
As for reccomended characters, Pet Pal on the Red Prince is nearly a must. Fire slug fun will be had in the first act and it will make an Act 2 quest quite easy. Red Prince gets the Lizard bonus Persuasion. This is the only point in Persuasion you need for the first act. Anything that needs more can be failed without loss of XP. Fane can be a good choice for new(er) characters. Keeping Fane as a ranged character is likely best as it can be a bit difficult to keep an undead alive when you are new(er) to the game. However, watching the game try to take out your own undead will teach you to better handle the many undead you will encounter in the game. Also, there is a book in act 2 that can only be read by a character with both Mystic and Scholar traits. Fane ticks these off and is the only origin character to do this. Once you get to the Lady Vengeance, you can optimize your party's civil abilities. Fane is undead, give him Thievery and you don't need lock picks any more. With act 2 loading a character up on persuasion is recommended. Having a human character maxing barter is a good way to make more money when you sell things and spend less when you buy them. Just keep in mind only the character with bartering gets these bonuses, so that character will be your main interface with vendors.
As for classes to play with Fane and the Red Prince, with my party, their default classes work well. The Red Prince works well as a strength base fighter because the lizard breath can be use to do some magic damage providing your opponents aren't immune to fire damage. A Warfare/Geomancy build works great for the Red Prince. As for Fane, any type of mage works well for him. However, as undead, the default Wizard set up gives you Geomancy and access to the game's poison spells. Taking Lohse or Ifan as a Wayfarer works perfect in my build. Wayfarer gives them Pet Pal, Bartering as a civil ability, some points in Finesse and a bow to start with. From that start, just push Summoning and Finesse. That leaves a 4th spot for Sebille or Beast. Honestly, Sebille is perfect as a Shadowblade. Beast gets the dwarf +5% Dodge bonus and thus makes a good melee character. A Battlemage is perfect for Beast as you can play the Battlemage strength based and do some tanking or intelligence base and a bit more like an actual mage. Beast is great set up as a Cleric as well. However, if you have already chosen a Fane as some type of mage, the Red Prince as a strength based fighter and Lohse or Ifan as your Wayfarer/Summoner, then I would likely go with Sebille as a Shadowblade. Another reason would be due to their respective back grounds, watching the comments Sebille and Red Prince have for each other is funny.
Try to get Lucky Charm on a character. You will find a lot more loot once you have a couple points in Lucky Charm. As a tip, keep booze (beer and wine) on the character with Lucky Charm. If you have a bunch of barrels, boxes, etc in an area, drink some booze right before opening the loot containers. Booze will make you drunk which drops your intelligence for 5 rounds, but also boosts your luck by 2 for 3 rounds. Rounds 4 and 5 must be the hangover.
Chug that booze and then open as many loot containers as you can before the boost to Lucky Charm runs out. A side effect of a lower intelligence could mean you character is no longer capable of equipping some gear. This means the character may have to take some gear off when drunk, which can be add some humor of the game. Please don't change this Larian, it is working as intended, in my opinion.
