So for my first game, I chose a random advanced start and ended up crashing on the Peltian's planet. Shortly after escaping, my next action was to take the quest to grant spacefaring to the Burlusts; they have really high compatibility with their planet, and seem like they'd be good allies.
After that, I was looking at ways to make friends with them. Turns out, the best way is to roll into town, murder the prime warlord, and makes friends with the NEW warlord. So, fully expecting to die, I challenged the prime warlord as my second ever combat.
Short story: Warlord battles are too easy, and also too grindy.
Longer version: Normal combat difficulty. For starters I thought I'd take him head on. Full power to shields, let's trade blows... oh, after one turn my shields are gone. Nope nope nope nope... How about full power to engines and I'll circle strafe him. His only weapons are slow bullets and slow missiles... oh look, that works.
So for 5 million points of damage at a rate of about 70k damage/turn, I circle strafed the warlord to death. At no point did he remotely challenge me, except one moment when I learned the hard way about his gravity lance.
My suggestion: Warlords, with their somewhat unique roll of solo boss battles, should probably have some very unique and challenging weapons. More than any other encounter, these guys should be throwing bullet hell patterns of death at you. Certainly, considering the seemingly huge reward for beating one (the Burlusts now seem to be my BFFs4life), it should much more challenging to do at the very start of the game.
I'd be greatly in favor of ratcheting up the intensity of these fights in general - give them less insane amounts of health, but make it hard to survive long enough to take out what health they do have. I feel like they'd be more compelling as a "glass cannon" kind of boss; they certainly aren't very interesting as an "armored hulk that can't actually hit you" boss.