A 4-core radiator or an aluminum unit will do wonders. Summit has "Direct-Fit" aluminum units that work well and are reasonable priced.

On the timing issue (sorry, just got back to this thread), you mentioned you advanced the distributor to get highest idle. That puts you in the ball park. Now what a vacuum advance unit would do, when hooked up to full manifold vacuum, will add another 15 degrees of timing at idle. So your initial timing remains low to allow the car to start, but after you start it, the vacuum advance pulls it beyond what the mechanical can do. On a hot running engine, that's what the TVS (thermostatic vaccum switch) did on the 69-up Pontiacs. The switch was mounted in the intake manifold water crossover, and has vacuum hoses sticking out of it. When the engine ran hot (over 210 degrees I believe), the switch would activate, and the vacuum advance would pull another 15 degrees of timing until the engine cooled down. Lots of old Pontiacs don't have this switch anymore, but that's ok, we use full manifold vacuum all the time, or ported vacuum with modified distributor curves.

You don't need this switch for your overheating problem. I was just referring to it as to why brand new Pontiac 455's ran cool when new.

You may want to think about a better radiator. It's tough keeping a a 2nd gen car cool with a 3-core and a 455.