I would, if Iwere in charge, do the following:

Definitely do a full remastering job in HD; not an automated process (see DragonballZ for how that turned out), but a full-out remastering. Then I'd examin the remaster, along with a few other star wars fans, and see if there was anything they missed and/or needs t obe touched up ever so slightly.

The deleted scenes would not be forgotten.

Those guys who did the Blade Runner DVD would be my consultants as to how to do the set.

I would just keep the old footage, and not reshoot anything.

Do MILD grain reduction. Enough that it's not intrusive, like in the shot linked http://jedi1.net/jedi1.net/images/1600/ANH-C-3PO-02204-1600.jpg

And that's it, for me. Oh, and of course I'd ask you guys for your opinions.