Why is my relay oscillating for over a half-second?
This kind of oscillation is called "chattering". 

To avoid this you should add bypassing across the 5V line to ground (maybe 1uF ceramic in parallel with 100uF electrolytic). 

Add a 100nF across the variable resistor. 

And add some hysteresis. That is a bit difficult to do with your present circuit, one way is to add a PNP transistor as follows: 







simulate this circuit &ndash; Schematic created using CircuitLab

Pick Rx to add a bit of hysteresis compatible with your desired switching points.

You may wish to try this without the 100nF or add a series resistor to the base of perhaps 5-10K and retain the cap across the variable resistor, to keep from slowing the positive feedback.  Basically you want the hysteresis to take effect immediately and the changes from the variable resistor to be slowed a bit.