Just as a couple of general comments to start-off... There are solid state relays that are rated for currents well over 100 A, but for maximum currents above ~5 A they get costly in a hurry. Also, you are right that ideally the fuse should fail before the relay. Therefore the relay probably should have a rated maximum current above the fuse's value.
You didn't mention the voltage level or if it was AC or DC, but I'm presuming since these are Christmas lights they are being powered from the mains and since your location is Florida, that's 120 VAC. If these presumptions are true, there is an alternative method if you just want to switch the entire LED array on and off, a PowerSwitch Tail II. Now if you want to do things like dimming or flashing specific LEDs on and off you'll still need a relay, or perhaps high voltage MOSFET, based control circuit.
Edit: PaulS is correct that the fuse could be well over rated for the actual current draw, the fuse's main purpose would be to prevent an electrical fire. However if it's pratical to have a relay with a higher maximum then you eliminate the possibility of replacing a relay before the fuse. 