What settings will preserve quality when I output an edited .mp4 for Youtube upload? EDIT START
While the links below suggest solutions in line with what I'm looking for, testing the solutions (H.264, Lossless Output, etc) results in near-identical results to my problem examples. While I continue to experiment with this, the information provided as answers have failed to have any impact on the issue at hand.  Is this unavoidable? Is Blender, then, unsuited to editing such footage? Should I use a different program that doesn't need to re-render the footage? Or should I make my initial recordings with far less compression?
EDIT END

Original file, captured from I Am Alive with Open Broadcasting Software.


Edited file, output from Blender... (note the heavy artifacting and colour compression in the well of the desk, just above and to the left of the girl's knee - now a uniform green rather than gradients of brown)

...with the following settings (informed by this page):


Does anybody know of a way I can edit a video in the Blender VSE without losing so much information and gaining so many distracting artifacts?

(Also - I know this is unlikely, but... is there any way to edit (eg. snip a bit off at the start and end) a video without having to re-render the whole thing? Takes so darn long...!)

All the best,

--Rev
Work from the best quality sources you can, and keep the work in EXR stills format until you are ready to conform the work to a master.
BINAC: Blender Is Not An Encoder. The bulk of your issue here is largely because you are relying on the various encoding settings from within Blender. Blender is not and should not be considered an encoder. Work from step 1 and provide a series of still images that your conformer can work with. For example, outputting to 100% quality JPEGs from your EXRs and then encode them with FFMPEG. FFMPEG offers many preset configurations that will deliver results that are leaps and bounds better than Blender's encoding defaults, as well as provide you with the flexibility to encode shot by shot if required to a suitable format.


For more information as to the low level internals and the whys regarding the above, you can see an answer I have posted here. Good luck.