This is just a quick question, does anyone know why in English, French, Spanish, and Portuguese (and any languages I missed) the "soft" g sound and the j sound correspond?

Besides the normal process of language change? /g/ palatalised before front vowels in the Vulgar Latin underlying all of the Romance varieties you mention and fell together with /j/ (spelled <I> in Latin orthography, but later <j> to distinguish it from /i/).

<J> wasn't part of Old English orthography; Modern English words containing <j> were originally borrowed from French along with the French pronunciation. (/g/ also palatalised in English, but the outcome was spelled <y> instead of <j>, e.g. ȝear > year.)

It's also interesting that, for example, an old Czech orthography used <g> for /j/. Perhaps it's true for other medieval Central European orthographies as well, but I don't know for sure.
Till the XIX century, Polish used to borrow some Latin words with <j> in place of <g>: jenerał from generalis, trajedia from tragœdia, rejestracja from registratio, regestratio, rejent from regens, jeniusz from genius. I have no idea why, nowadays many of them are spelled with <g> and pronounced with /g/ (generał, tragedia, geniusz), in a few cases there are variants (agencja~ajencja, rejon~region*) with slightly different meaning or <j> (/j/) has won (rejestracja 'registration'). There hasn't been any sound change of the kind that would affect similar native words.
EDIT: I did some googling and there were several mentions of some medieval Latin pronuciation with g > j before front vowels. How could that arise, though? And the forms with g were said to be "restored by renaissance humanists".


*however, according to my dictionary of foreign words, rejon may be from French rayon, rather than from Latin regio.