I've also got a S370 800/256/133, but since I haven't got a cooler, that's irrlelevant at this point.
So which chip will be faster? I assume the 600/512 will have a decent amount of speed since it's got half a meg of onboard, but the 667 has the extra 33Mhz...
The board and RAM are both 133 capable so that's not an issue at all.
I think the first one would do you the best (the one with 512k cache). If the board supports smaller FSB increments you could try pushing up the bus speed as well, but keep an eye on the PCI/AGP dividers.
It's only a 10% increase in clock speed, whereas its a 100% increase in cache. I could be wrong, but I'd choose the first one and clock it up a bit.