While it certainly doesn't make sense for them to be there in the first place, couldn't you just skip past needing an explanation for the droids being there by starting the movie with them already in the palace, ala Lando. Threepio is already Jabba's translator, and Artoo doesn't even appear until they head out to the sail barge.
Smuggling Han out of the palace is a horrible idea to begin with, since it is a heavily armed fortress. Getting everyone out to the open air on the sail barge is a far better plan, especially with skiffs to steal.
Why can't the plan start with getting everyone inside Jabba's palace?
Lando, Artoo, and Threepio don't need an intro of how they infiltrated. They're just there to start the film.
Leia is disguised as a bounty hunter with Chewie as bounty to get both of them in. Leia "botches" the rescue, which is needed to free Han from the carbonite. There isn't a plan they could come up with that would have been better with Han remaining in that block, and they needed to be able to evaluate him to see if he could even do anything once they got him out. Maybe even imply Threepio ratted out Leia. Jabba wanted Han alive the whole time (witness Boba Fett saying that he was no good to him dead), so surely they could count on Jabba not immediately executing Solo. Change Jabba's dialogue to promising Leia a fate worse than death to explain why she doesn't get imprisoned in the cells like Han and Chewie.
Luke is the last to enter. Maybe use the audio from his now cut hologram to have him make his offer to Jabba for a peaceful exchange. Jabba, who has been shown to prefer torturous and unique execution methods (leaving Han in Carbonite, and Oola the dancer going to the Rancor), will surely not just shoot Luke and be done with it, instead he feeds him to the Rancor. Luke slays the Rancor, and Jabba goes with the almighty Sarlaac.
Now you have a slightly recovered Solo that can actually participate (even if just a little) in any action. Lando, as a skiff guard, is in perfect position to help take over their skiff to escape.
The only real blip in their plan is that Jabba doesn't slate Leia for execution like the others, keeping her with him. That necessitates the bloodshed to rescue her, and it has to happen right there, as they won't get a second chance to escape. The Rebels are also preparing to attack the new Death Star, so there won't be any help from them.
It's not that great of an idea, but I think that any plan that goes with the thought they're going to walk or even fight out with a Han they don't even know the condition of is ludicrous, thus why the Sarlaac was the only option for them.