@Darudius
Correct.
The only one who actually wanted Gideon to leave gone was the Sage, who wanted to mack on his little sister without Gideon around. Although the chat between the Literal Lancer and the Grandmaster implies that part of the problem was that the Grandmaster tends towards brutal honesty when critiquing someone in a fight, so he apparently said something a bit rude-but-true about Gideon not being able to keep up with their current fights. Unlike the Sage, though, he fully appreciated what Gideon did for the party.
Even though he never would develop any of the Fancy Advanced Skills the others were starting to develop once they outleveled him, Gideon provided his Little Sister Hero's party with diplomatic support, managed all their supplies, gathered intelligence on what they were doing, made sure they weren't sick or injured, and was in charge of their Mook Support when they were working with armies and planned their strategies. Hell, he used to be the Vice-Captain of his own Knightly Order, which means he could potentially bring Elite Mooks along too for fighting lower ranking demon fodder. That doofball Gideon forgot that not everything is raw stats, since even if he lacked Flashy Super Mega Sword Magic Beam moves, he was still a quite experienced fighter by that point who has plenty of experience at using what he has. IE, he one-shots the Owlbear early on in his retirement with just a basic sword attack combo'd with a low-ranking movement skill.
Basically, Red used to be pretty much all the Support-type jobs (Inventory management, rumor gathering, out of combat healing, equipment acquisition, etc) you find in a Suikoden game, all rolled up in one person.
Sage basically sucker-punched him, emotionally, and convinced him to leave quietly without the rest of the party knowing while he was feeling bad about not being a frontline fighter anymore. This is doubly stupid because as the Heroine interlude points out, she's getting to the point that NO ONE can keep up with her, so Red not being able to do so is another reason the long time party members are pissed at the Sage swindling him into leaving.
This has backfired AMAZINGLY badly for the Heroine's party.
Not only did they lose the extremely powerful high elf druid (who nearly killed the Sage in a magic fight as well as devastating the area when she started doing the whole 'summon Greater Elemental' thing after calling him out on being full of shit), the Sage is -horrible- at the jobs that Red used to do. IE, the party is stuck in a desert because Alex the Sage pissed off the local sand people, didn't stock enough supplies, and doesn't know where the Relic Equipment they're searching for is (because he hasn't done any background info gathering before they arrived and also pissed off the locals who might know).
On top of that, there's a decent chance that part of his Job wasn't 'just' guarding the Hero and their party while they were weak. Chapter 6 mentions that Jobs have a mental component as well, with people gaining personality quirks from their Protection/Jobs as they grow into and level them up. The Hero's job, from what an acquaintance who's read ahead points out, makes them mono-focused on Killing the Demon Lord. The speculation we've got is that part of the Guide Job's secondary effects is it smooths out the edges in those around them. IE, if you look at the flashbacks, Gideon shows up and helps inspire people to not give up, find a way out of hopeless situations such as Lit's with 'We're besieged by a demon army and a shapeshifting demon murdered our highest ranking general and led our forces into a trap' moping, that sort of thing. Hell, Red even does it on a minor level, such as inspiring the Sauna owner to not give up at competing with the super fancy new onsen, or reassuring the little kids that their Protections do have an influence on personality but aren't something to be scared of, just aware of.
It's one reason his little sister seems to be getting scary enough to intimidate the Strongest Grandmaster Martial Artist with a single death-glare, as well as getting apathetic about things that aren't killing demons. Without the Guide around, she's getting more and more focused on 'MUST KILL DEMONS', since apparently the Hero Protection causes some extremely strong personality urges without moderating influences. Lit mentions that she couldn't really comprehend Ruty the Heroine in SERIOUS FACE MODE (Lit considers Ruty scarier than any demon she's fought) with the little sister snuggling up to her big brother, so she is notably different around Gideon, which supports that possibility of the Guide Protection having secondary effects.
The other reason she's getting super scary is probably a chronic lack of Headpats from Oniisan. Very important for an Imouto, those headpats. Seriously, end of Chapter 6, she's got the rest of her party staring at her, with an entire demon army murdered, muttering 'I AM STRONGER NOW. PLEASE PAT MY HEAD ONII-CHAN' and making a scaryface.