The problem with your circuit is that the load resistor is mismatched to the resistance range of the sensor you care about. The sensor in series with a resistor gives you a voltage that varies as a function of the full sensor range, from 0 to ∞. However, the resulution is highest in the middle of the range, which is when the sensor and the load resitances are equal.
Therefore the solution is to use your top circuit but make R1 640 Ω instead of 10 kΩ. That also produces a low enough impedance signal that you can directly connect it to the A/D input of most microcontrollers.
With a 640 Ω load resistor you get 2.58 V at 600 Ω and 2.22 V at 800 Ω, for a 360 mV difference between the two light levels you care about. With a 10 bit A/D, which is common in microcontrollers nowadays, that's 73 counts. Many micros are available with 12 bit A/D now, which would get you over 290 counts, or about 1/3%. That's more accurate than your LDR sensor.
my DC power source is via a full-wave rectifier without a capacitor,
so there seems to be very small fluctuations in the DC voltage. Would
that be the problem?
Yes. Without a capacitor to smooth out the rectified AC, the voltage will go up and down at twice the mains frequency. This is why the relay 'buzzes' - it is turning on and off in time with the rectified AC.
How do I ensure the relay only switches once when light slowly fades?
Most relays have a large hysteresis (pick-up voltage > 3x drop-out voltage) which in your unity gain circuit should be sufficient.