I have several WeMos boards running 24/7 on a tiny 5volt cellphone charger plugged into the USB socket.
Never turning them off will fix your startup problems.
With an Uno/Mega/Nano, that can have that same behaviour with certain relay boards, you have to digitalWrite a HIGH to the pin BEFORE setting the pin to OUTPUT with pinMode.
Not sure if this works with an ESP8266.
Maybe you should have posted a link to the relay, and your code (inside code tags) for better help.
Leo..
P.S. The NodeMCU has 4MB of flash that you can write to (SPIFFS).