In wie weit des mit einem Widerstand vor dem Relais reicht, müsste man probieren. Der passende Wert hängt auch vom Relais ab. Der Widerstand darf von der Leistung jedenfalls schon mal deutlich kleiner sein - so 1 W, ggf. sogar 0,5 W sollten schon reichen, hängt aber vom Relais ab. So grob von der Größenordnung wird das Relais etwa 2 VA brauchen, also rund 10 mA - im nicht angezogenen Fall ggf. auch mal etwas mehr. Um die Spannung für das Relais dann so weit zu reduzieren, das es deutlich langsamer wird, sollten am Widerstand vielleicht 50 V verloren gehen - das wären dann 5 K Ohm. Damit hätte man schon mal etwa die Größenordnung zu probieren. Eine wirklich saubere Lösung ist der Widerstand vor dem Relais aber nicht - das müsste dann auch schon ein NTC sein, nur halt für weniger Strom.

Eine elektronische Lösung wäre ein Kondensatornetzteil für das Relais, damit einen Elko laden und erst ab einer gewissen Spannung im Elko das Relais per Transistor auch wirklich einschalten. Das Relais sollte dann aber wohl besser eines für DC (z.B. 24 V) sein.