Is the 'fore' in 'forewarn' redundant?
Solution 1:
I agree with the 'timeliness' implication. There is a clear real-world difference between
“Watch out - lightning!”
and
"Do not sail now, the seas will be rough/the weather will turn inclement.”
Both "warning" and "forewarning" counsel caution, but a forewarning necessarily arrives in time and counsels precaution. (Which seems to be the sum and substance of the saying forewarned is forearmed.) Forewarn is thus a better choice of word to connote shades of 'prophecy': you may 'warn' because you see danger, but you 'forewarn' because you foresee it.
When I imagine somebody saying “We were forewarned,” I sense the voice of gratitude, but "We were warned” is a mere statement of fact. Allowing for inflection, the distinction between the two words is gravitas.
A couple of points on the polysemy of Warn:
a) Warn can easily stand in for “threaten” in some usage contexts.
b) A warning can be issued after the event has come to pass- in a legal context, a judge’s warning to a first-time offender guilty of a minor misdemeanor.
Solution 2:
I agree that forewarn and warn are pretty much synonymous. One place you can't interchange them, of course, is "forewarned is forearmed". That's a set phrase, so the words can't be substituted.
The main difference seems to be that while you can warn anytime before an event, you can't forewarn just as the event starts. For example: you can warn of a landslide when you see the rocks start to shift, but by that point it's too late to forewarn.
If you look at etymonline you can see that warn comes from a word meaning "to give notice of impending danger".
The OED says, similarly to etymonline, that forewarn comes from the Old English meaning of warn: "To take heed, be on ones guard, beware" which indicates an immediateness, and the prefix fore-, which is from Old English and indicates something like "the earliest time".
So the difference around the time of coinage may have been that warning happened at the time of danger, and forewarning happened earlier, possibly (as the OED states) as a prophecy, or just as advice long before the issue arises.