What size should my header image be?

Your header image is the main background image at the top of your profile page, so you'll want this to be of a reasonable quality.
It needs to be less than 5MB, and with minimum width of 1400px.