koma við þat út

'at koma út' just means to travel to Iceland. I guess the phrase
must go back to a time when the settlers still thought of themselves
as basically Norwegian at heart. The opposite is 'útan',
literally "from out", but in the context of Iceland "abroad".
(Zoega út 3, útan 2.)

'við þat' I think just refers back generally to all the magnificent
things they've getting up to in on those gallivants. "With that
[done], they come home." Gwyn Jones has "AND SO they return home
again".

ok þykkja þar mestháttar, sem þá koma þeir
and are thought so very important wherever they come then

þar...sem
"there...where"
"in-whatever-place...that"

Gwyn Jones leaves out "then". Maybe it refers to the time after
they've done their travelling, now that they have a reputation
they're thought important, once they've been from land to land.