Cyclone III AS configuration bizarreness

I just can say, that PS configuration is generally operating, also with C III. It doesn't require any delay in addition to the specified timing. I don't know exactly, at which points the serial bit stream is checked for errors, but I expect that you have either a problem at the physical level (signal quality, e.g. ringing DCLK) or at the logical level (wrong data). That probably sounds banal, but it's likely anyway.

Personally, I would never design a board without a JTAG interface, at least accessable at test points. The issue may be caused, by the way, also by floating TCK and TMS inputs, they must be hold during power up and programming at their idle levels.