Maybe if Jedi starts with the emperor's arrival, there'd still be a star destroyer at the beginning? The whole second death star thing is a pisser. "Spreading it around" like this is cool, and could help. Maybe it wouldn't feel like such a re-hash if the briefing scene is somehow re-cut to grimly emphasize that this time it's an ASSASSINATION. Killing the emperor is the goal instead of another death star graphic, another "knock out the main reactor blah blah" speech...
Well the way I'd envisioned it was the Emperor arrving on the DSII after Luke's conversation with Obi-Wan. "They do you credit, but they could be made to serve the Emperor..." wipe to Palpatine's arrival. Also, the entire opening of RotJ (Star Destroyer and all) would be used in ESB, so there wouldn't be an available establishing shot for the Emperor scene as the first shot of RotJ. On the other hand, if we wanted to go that route, it would be a lot more complicated, but we could rethink the openings of both movies, altering RotJ's to transition into Palpatine's arrival, and reference his visit to the DSII in the last paragraph of the opening crawl.
The idea of an assassination is brilliant! It would definitely make the Death Star attack seem fresh and not ANH-Redux. Looking at the conference scene, it would appear the only way to get this point across would be to re-dub and subtitle Admiral Ackbar. I know his voice is a fan favorite, but it would match with the now heavily-subtitled prequels as well. In fact I think almost every alien race would speak their own language, which makes sense. How can they understand each other? Who knows, it's sci-fi/fantasy. Also the cult line "Many Bothans died to bring us this information" would best be cut to smoothly transition from Mon Mothma's announcement of the Emperor to Ackbar's assassination speech.
EDIT: Over in the General Star Wars section there's an interesting debate happening about the actual timeframe of the movies, i.e over what length of time do they each take place? The most problematic film is ESB - how long is Luke training for? How long does it take Han and Leia to get to Bespin? Irvin Kershner says it takes place over a period of a few months, yet the characters don't even change their clothes. Are there any plans to address this issue in the Starkiller edit? (not the lack of a change of clothing, but just the ambiguity of the passing of time). Apart from a caption reading '2 months later' I can't think of any ideas, but maybe you guys can.
Who's to say they just didn't wash and re-wear their clothes over the time span?

Seriously though, we wouldn't use a caption card or anything like that. That would not fit at all. Could alternate dialogue somewhere help out? What and where I have no clue. This is definitely something wort addressing though. Obi-Wan trains for 20 years, Anakin for 10, and Luke for (what seems like) a week? I don't think so.
Also, now that we're talking about briefing scenes, is there any chance of replacing the DS graphic in the ANH briefing? I'm half cringing as I type this just from being used to it (and they are kinda cool in an old school way), but given the quality of the graphics in AOTC and ROTJ, the only explanation I can see for them looking like that is the status of the Rebellion at that point. They were just winning their first big battle, so that could definitely go for the explanation, but if you don't want to go with that and if it's feasible, it might be something worth looking into.