Lobster's airship is crewed by a gang of cats and he has a very possessive butterfly that follows him around.

BUMPing this because I have no idea what game this is but I refuse to let this fun forum game die down.

@muddysneakers What console generation are we talking here? 32-bit? 64-bit? PS2, PS3, current?

This is PS2 but the main series spans PS2-PS4 and handhelds.

I think we're in France because everyone's names are French. There's also a lot of religious symbology and both my name and my crush's name are religious words.

Tales of...?

Nope this is a spin off of Disgaea.

Makai Kingdom: Chronicles of the Sacred Tome

Nope. Maybe its an unofficial spinoff. There is lots of crossover of characters. Its listed in the wiki but not under spinoff games.

Guys, girls(?), please help. We have to identify this game and move on.

La Pucelle: Tactics (hopefully it is, please tell me that's it...)

Stop playing with yourself, Then.

HUE HUE HUE HUE HUE

Winner. I promise never to choose such an obscure game again.

Haha, at least it seems to be a cool game. I kinda want to experiment playing it sometime now. But this is why I usually try not to choose console titles here.

Anyway, off to the next challenge.

I am part of an elite force that was about to attack a boat full of demons. Unfortunately before we could do it some stuff happened and now my mates are all separated in this region that somehow exists underwater. At least it appears I will find a human settlement down here that could help me and use my help while I find and regroup my crew.

Dark Queen of Krynn?

No.

New hint: This game has more than one playable character, but you pick one and stick with that choice until the end (or at least very close to the end. Since I didn't finish it I could be surprised by a character swap near the end but I don't think so.)

My previous hint's description could match any of the playable characters.