To save someone a little time, here are two ways I was able to successfully send requests and get a 200 response. I was getting 406 because I was relying on my server sending HTTP_ACCEPT_ENCODING, which is apparently not enough.

Using cUrl:

// create curl resource
$ch = curl_init();

// set url
curl_setopt($ch, CURLOPT_URL, "http://api.discogs.com/release/1111");

//send headers
curl_setopt($ch,CURLOPT_HTTPHEADER,array('Accept-Encoding: gzip', 'User-Agent: ExampleBot/1.0'));

//return the transfer as a string
curl_setopt($ch, CURLOPT_RETURNTRANSFER, 1);

// $output contains the output string
$output = curl_exec($ch);

// close curl resource to free up system resources
curl_close($ch);

echo $output;

Using PHP get_file_contents (Thanks vreon at Discogs):

$ctx_options = array('http' => array('method' => 'GET', 'header' => 'Accept-Encoding: gzip, deflate\r\nUser-Agent: ExampleBot/1.0\r\n'));
$ctx = stream_context_create($ctx_options);
echo file_get_contents('http://api.discogs.com/', false, $ctx);

Of course, make a up a unique user agent.