Thought:

We don't actually need anything in Jabba's Palace until Leia & Chewie arrive. If you establish in the crawl that folks are already infiltrating the Palace, then Threepio's presence is explained. Artoo, meanwhile, we don't see until he's serving drinks on the barge. Threepio's reaction is sufficient to introduce the idea that Artoo has infiltrated the Palace, much like Lando. This opens the door for Luke & Yoda moving to the beginning of the movie without problem (seeing as he needs Artoo with him in the X-Wing).

I had concerns about how this removes the introduction to Jabba and his Palace that the droids experience, but it may still work. I'd recommend an establishing shot of "Boushh" and a chained Chewbacca walking towards the Palace before cutting to the dance inside.

The only real problem I see is that Luke will have waited an awful long time to actually ask "Is Darth Vader my father?"... and what to do about everything once they return to The Fleet. I mean, Luke's current introduction is pretty nonsensical, but how to fix it?