I also tried Norse UHV and Vinland was absolutely doable on monarch. One doesn't even need to send the start settlers far away. I guess, if i didn't want to build the Uppsala Shrine, all 3 UHVs can be done around 1050.
By the way, I really dislike the 'reveal all ocean tiles' UHV, it's annoying to manual galleys around empty tiles every game. Of course I can choose not to do that, but if I want to win a UHV, this map thing is very not fun beyond the first time. Can we change it?