I had my head gaskets go in my '99 STI, while the motor was out I did the following;

- Had heads serviced by reputable workshop (The Engine Shop, Canning Vale)
- Cleaned up block faces
- Replaced head studs with nitrated Subaru items
- Replaced Cam Seals
- Replaced coolant hardline that runs up and over the block from the thermostat area due to corrosion
- Replaced every single coolant hose and hoseclamp. Used genuine Subaru hoses and worm-drive hoseclamps. Do not reuse the springy original clamps, I had one leak despite cleaning the hardlines and using aviation paste and had to pull the manifold off again to fix it...
- Replaced intake and exhaust manifold gaskets & turbo gasket
- Replaced any old looking vacuum lines (be aware of the restrictor pill in the lines near the turbo wastegate, probably best to leave those alone)
- Fitted aftermarket alloy radiator
- Fitted Group N engine mounts
- Replaced brake booster due to signs it had been leaking
- Painted around the battery tray where a battery had once leaked
- Cleaned up wiring - replaced conduit & retaped
- Painted engine crossmember & steering rack
- Cleaned and cleaned and cleaned and cleaned everything I could get my hands on

A couple of things you could do that will be made a lot easier by having the motor apart are;

- Fit a silicone under-manifold intake pipe (~$250)
- Fit a 3 port oil catch can/Air Oil Separator (can use the hard line that runs under the manifold, a lot easier to set this up with the manifold off the car) (~$350)
- Fit Group N Engine Mounts (~$100 from Maximum Motorsport)
- Fit an oil pressure gauge sensor onto the block
- Change out spark plugs & leads
- Change rocker cover gaskets (use genuine Subaru gaskets)
- Fit ARP head studs (If you're still running the standard motor, ARP 2000's will be fine) (~$300)
- Fit a sump baffle plate & aftermarket oil pick-up (Killer B offer these parts, make sure you get them for the correct shaped sump!) (~$350)

Exedy OEM replacement will be fine if you're running the 5 speed.