You just need to change the header image size in your functions.php file and then it will allow you to upload without having to scale –
// Add support for custom header
add_theme_support( 'genesis-custom-header', array(
'width' => 360,
'height' => 120
) );