Indeed, the early Norman kings of England used to go to Paris and make feudal obeisance in their capacity as Duke of Normandy to the King of France. As the French will never shut up about nowadays.
I'm not convinced Harald Haadrada could have conquered England considering the Normans were coming. They might have ended up dividing it with Haadrada having the north and William the south (I remember one timeline posted on the frontpage of this site
MANY MOONS AGO which did this). If you want Haadrada to win the whole thing, you could play with the weather (if this is allowed) so William lands first, Harold Godwinson beats him, and then Haadrada lands in the north and the whole thing plays out in reverse to OTL, with Godwinson's tired army falling in the north to Haadrada.
Obviously a conquest by Haadrada would be far less traumatic and dramatic to the country than the Norman Conquest, because England had been ruled by a Viking dynasty in living memory and indeed historians in TTL might view Edward the Confessor's reign as being an aberrent blip in England's history of close ties of government to Scandinavia.