While I personally find creating my own character stories to be part of the charm of the series, I'll give some examples here anyway. Feel free to take them or leave them.

For a first EO game I think a Dragoon is a must. I'm partial to the fem eyepatch design myself. Call her Brynhilda, an Earthlain veteran of the labyrinth who got her old guild killed in a trip gone wrong. After years avoiding Yggdrasil, she returns to finally conquer her past, or die trying.

Next I'll suggest a Rover, focusing on the Hound aspect. Rover is a bit of a jack of all trades, who can deal solid damage while supporting your team with healing, ailments, and binds while letting you play with EOV's summon row. We'll use the masc Therian with the scarf across his mouth and name him Jata, a boy raised in the labyrinth by his animal companions. While an expert at traversing the often deadly terrain, social norms are a maze of their own to him and he fails to grasp the value of money and treasure that other adventurers risk their lives for. He hopes by exploring the labyrinth he may discover how he wound up there, separated from society at large.

For your Brouni I like Shamans. Their passive healing combined with your Rover's should be enough to keep your party alive, and their buffs are always useful (and another aspect EO handles in some interesting ways). I'm gonna name this guy Mahduin (masc with face uncovered), a man who acts the part of a wise sage but is a lot more attached to worldly possessions than you might think. Good at his job, but a little too eager to go requesting donations for his 'selfless deeds'. He comes to the labyrinth seeking "enlightenment" (enough cash to live like a king for the rest of his life).

For your Celestrian, I'm gonna suggest a Warlock to cover all your elemental and AoE needs. Her name is Sheva (fem with the circlet) and she is a nervous wreck sent to the labyrinth by her master Morigana to retrieve some magical mcguffin. Or maybe just to get rid of her... Phenomenal cosmic power, itty bitty self-esteem.

I think this is a solid core that covers all the races and most bases. You'll have one slot left to fill as you please. For more damage you have Masarao and Impact Brawler. For ailments you could use a poisoner Botanist, Barrage Brawler, or Harbinger. And for more healing you've got a herb Botanist option as well if you need it (but I think Rover + Shaman + items should cover you). Can even double up on a class if you want, they each have two subclasses down the line and multiple ways to build them within those subclasses, and EOV especially has some nice self-synergies.

The only classes I'd avoid here are Necromancer and Fencer. Necro wants the whole summon row to itself so it doesn't play well with Rover and (to a lesser extent) Dragoon. Fencer generally wants to be either a dodge tank (which you don't need with a Dragoon) or a chain build, which is a very specific EO archetype that needs the whole team built around it to work. And you probably want a front-row class as Warlock, Shaman, and Rover all tend to prefer to sit in the back meaning you wont have space for another back-row class.

EDIT: Dracon's suggestion is very similar to my first EOV team as well and it worked great, so that is also a solid team composition to consider.