Sengoku Rance

Basically you need to attack Uesugi and choose to kill the messenger when you get the chance. You can accept the offer but you get a rather sad rape scene and no Kenshin or Naoe Ai

I managed to beat the game without too much trouble (retrospective, it seemed like a real bitch the first time) and I don't recall anything like that, so I think you may have done something wrong, or you may just be attacking in the wrong direction.

This is how I recall it going down:
After a hellish battle in Cairo, I went on to Morocco, after two victories in morrocco, there is an event that sets in motion a timed game over. You need to take the rest of Morocco and fight at the bridge in Morocco, which is an event similar to the xavier fight halfway throguh the game.

Conquest order (refer to the wiki for faction specific stuff):
1. Hara (DUH!!!!)
2. Ashikaga (the battle against tokugawa is hard enough without character bonuses, the duel is just chancy if your good characters are dead from battle). Keep ashikaga in prison for later. Second seal.
3. Miko institute (why? Because Asakura has a 3000 man musket unit in the back ranks that usually tilt the battle meter. Granted at 50% field bonus, the mikos are no pushovers. Tanegashima will be explained later.)
4. Kenshin (level 63 right off the bat means bosses are already half way dead once she's out of moves from her alone... probably (except xavier, but only because he's lvl 99)). Third Seal. Takeda will now overrun houjo for the fourth seal. Save before you try for kenshin because...
5. You're forced into battle against Tenshi, which hopefully you've been able to run over kenshin about now, otherwise it's a two front war. If you find that you absolutely can't win two fronts, then just deal with tenshi before going for kenshin.
6. Tokugawa (?). Okay we've got everything we need, now we get Tokugawa's head. It's still a tough battle so you might want to save before war. It's pretty much implied you get Imagawa after this. This provides a solid power support (unless you recruit senhime, which will pretty much equal out the tokugawa gains).
7. Akashi (this causes mouri to overrun taneg, but I find them useless anyways, the real reason for this is so that mouri doesn't close the road to Takuga). This is the 5th seal so you'll need to go through the temple. Before you assault the temple, recruit ashikaga and trigger his purple event. Give the ring to Kenshin.

edit: Also, you need him to fight the one eyes later on because of a capture event.

8. You now have 10 turns to go beat people up. If you have to fight Iga, crush them fast, they have no good captains for you so don't waste too much time with them (you'll need suzumi in the final battle against Iga).
9. Takuga or whatever they're called. With about 10 or so turns after the temple, there's not enough time to get Takeda or Mouri, so lets make a last minute grab for good captains. These guys start with pretty absurd amount of troops, but Natori counters Gon (but you're screwed if he uses revenge the turn after) and uh... Ryouma doesn't do that much damage despite the unit size IIRC.
10. Demon army (okay my memory is borderline non-existent here, so I'm just going to make stuff up), demon army you can approach in many ways, but to sum up my strategy: I fought a stalemate war with them, retaking my territories and doing damage control. When I was certain I had 2 armies that can carry themselves, I stopped fighting the demon army and let them take whatever they wanted (they only attack you like once per turn anyways regardless of troops). I used battle permits so that the demon army net result was 0 territory taken or maybe 1 territory lost (they take it their turn, I take it back at the end of mine). I then used this time buffer to go and beat up Dokuganryu (masamune) (I did this after sill got frozen, and the duel with masamune vs rance was hell, so do this before she gets frozen), and used the 5 youkai commanders to completely slaughter the demon army.

Over the course of the game, before you push into the Amazons and Africa and before Sill is RFGed, you should focus on clearing out dungeons and getting levels so you can actually fight Xavier in the end.

SAT wise: First priority are allies, and the order that I find most useful is 1.Zeth (Rizna is slooowww, but she's stronger than kanami at least)
2. Zeth (Uruza, she's top tier and paired with Kenshin there should be no reason that you lose... ever)
3. Leazus (meh, you don't have much choice with this)
4. Leazus (Maria... she's practically a ranged musket unit)
5. Leazus (Leala is top tier, with like 500 guys and if you get her to str 9, she can crush like 1000 or so guys instantly, just don't let her fight serious battles against the demon army or go at them with 2 guard units on account of her capture trigger)
6. Zeth (there's no one left, and the only reason why you need this reinforcement is for Rance's love item)

Second priority: Reinforcement cost -1. You can do this up to 3 times, and yes it is worth it. It should be at -3 cost when you get to the demon army. This allows you to fight them until they hit the point where they stop attacking (provided you actually kill their captains and heavily injure their armies). Hopefully you won't need to get to that point on account of you raping them with the youkai captains.

Third priority: Rance upgrades. Try to upgrade Rance troops when he's around ATK 7 (2 from books, 1 from natori), for the most bang (because with a atk book 2, he'll be at atk 9).