A header image should always be added via the WP header image.
Xtreme background images is a different thing all together.
When you add a Header image with WordPress, you can skip the cropping to keep the image whatever size you want.
How big it should be depends on the design of your site.
If the site is set for a Maximum width in The Site width option, and if the Header or header image is not expanded to the full width of the browser, you only need an image as wide as the Site width you have set.
If you are using a Full width design where the header image will always expand to the edges of the browser, then you want an image big enough to cover the distance. and HD screen is 1920 x 1080, so a width of 1900 pixel would be a good start.