Easiest way is to pull your new halyard through when you pull the old halyard out. A small diameter high strength line tieing the two together with rolling hitches then taping over with masking tape or good old duct tape to smooth the join out to get away from snags is the way I do it.,\
Any of the big name Line suppliers make good quality line that will last. You are paying more for lower stretch and light weight, not necessarily longevity in the higher priced offerings. For a halyard, the lowest stretch that you can afford is best. Halyards are under pretty high constant tension and not the easiest to adjust when conditions change.
New England Ropes makes a reasonable cost, low stretch line called VPC, IIRC. It's designed to replace StaSet X and is a composite of Dacron and
Dyneema or some such exotic. It's lower stretch than the old cruiser standby StaSet X but way cheaper than an all
Dyneema cored line. Personally don't like StaSet X because of it's stiffness but it's the most economical line with somewhat reduced stretch. StaSet X is all Dacron but the
core is straight filament not braid which makes for less stretch.
If you want to get max life out of your lines, spec'ing them in Black will probably do more for longevity than anything. For some reason, Black resists UV degradation way better than any other color.