1) MOST IMPORTANT - dual exhaust. That factory single exhaust is restrictive even for the little V6! If not true duals, maybe a big single system, but duals are probably easier.
2) I would actually NOT recommend removing the EGR - it'll help with cruising MPG, while not detracting from full-throttle power. Use of EGR also allows for more aggressive timing.
3) If you have to get inspection,I'd leave the cats - or get some high-flow catalytic converters. Catalysts today are NOT restrictive like they were in the late 70s.
4) 4-bbl carb. Even with the stock cam, I'm told that going to a 4-bbl helps. On the cheap, using the 4-bbl intake (say from a 4.1L/252ci Buick V6 from the early 80s) helps. I think the carbs from those cars are all electronic-controlled, though, so an aftermarket carb, or maybe a retuned carb off a small V8 from the 70s, should do the trick.
5) If going inside - cams are as mild or wild as you want, and I don't really have experience with choosing a cam.
6) If rebuilding, I imagine that it's safe to go a little higher than the stock 8.0:1 and still be able to use 87 octane. I don't know how detonation sensitive the 231 is, though.
That's all I can come up with offhand. This is all "in theory" - I do NOT . . repeat, do NOT, have practical, hands-on experience in this. But I think the theory is sound. Well, with the exception of the dual exhaust - Uncorking the exhaust, I felt a real, noticeable seat of the pants difference despite the rest of the engine being 100% factory (on an ECU-controlled 1984 Regal 4-door)