MS Paint is underrated
JavaScript

This solution uses the HTML5 canvas element to extract the image data, but without the need to use HTML, that means it can be run in your console. It access the color palette image as an array; I stored all the colors from the palette image in an array). It outputs to the console (after it finishes) and also stores the result in a variable.

The most updated version of the code is in the fiddle. The fiddle also uses a better algorithm to reduce noise in the pictures. The improvement in the algorithm is mostly fixing a function (max to min) which caused the inverse color to be chosen.

Code in the shape of the MS Paint Icon! (formatted code in fiddle or Stack Snippet)

eval(`                                                   function                  
                                                        Paint(t){fun              
                                                         ction n(t){va            
                                                         r n=t.toString(          
                                                         16);return 1==n.         
                                                         length?"0"+n:n}fu        
                                                         nction e(t){return       
                                                         "#"+n(t[0])+n(t[1]       
                                                          )+n(t[2])}var a=ne      
                                                          w Image,i=document.     
                                                          createElement("canv     
                                                          as"),h=null,o=docum     
                                                          ent.createElement(      
                                    "canvas"),r=          o.getContext("2d        
                               ")     ,l=[],u=this,c      =[[0,0,0],[255          
                            ,2       55,255],[ 192,192,   192],[128,12            
                          8     ,128],[126,3,8],[252,13,27] ,[255,25              
                       3,    56],[128,127,23],[15,127,18],[ 41,253                
                      ,    46],[45,255,254],[17,128,127],[2 ,12,1                 
                    2    6],[ 11,36,2 51],[252,40,252],[12 7,15,1                 
                  2    6],[  128,127 ,68],[255,253,136],[4 2,253,                 
                 1   33],   [4,64,64],[23 ,131,251],[133,255,254],                
               [    129   ,132,252],[6,6 6,126],[127,37,2 51],[127,               
              6   4,1    3],[253,128,73],[252,22,129]];a.crossOrigin              
             =   "",   a.src=t,this.done=this.done||function(){},a.o              
            n   load=function(){function t(t){var n=0,e=0,a=0;return              
           t  .forEach(function(t){n+=t[0],e+=t[1],a+=t[2]}),[n/t.leng            
          t  h,e /t.length,a/t.length]}function n(t){for(var n=[],e=0;e           
         &lt;  t.l  ength;e+=1)n.push(t[e]);return n}function g(t,n){retur           
        n  (Ma  th.abs(t[0]-n[0])/255+Math.abs(t[1]-n[1])/255+Math.abs(t          
       [  2]- n[2])/255)/3}function f(t,n){for(var e=Math.floor(Math.ran          
          do m()*n.length),a=n[e],i=(g(t,a),1-.8),h=56,o=[];o.length&lt;=h&amp;          
         &amp;g (t,a)&gt;i;)if(o.push(a),a=n[Math.floor(Math.random()*n.length)]         
     ,  o.length==h){var r=o.map(function(n){return g(t,n)});a=o[r.indexO         
       f(Math.max.apply(Math,r))],o.push(a)}return a}function s(t,n){for(         
    v  ar e=[];t.length&gt;0;)e.push(t.splice(0,n).slice(0,-1));return e}i.w         
   i  dth=a.width,i.height=2*a.height,h=i.getContext("2d"),h.drawImage(a,0        
   ,0,a.width,a.height);for(var d=(function(t){reduce=t.map(function(t){re        
  turn(t[ 0]+t[1]+t[2])/3})}(c),0),m=0,v=i.width*i.height/4,p=0;v&gt;p;p+=1)d        
  &gt;2*Mat h.ceil(a.width/2)&amp;&amp;(d=0,m+=1),l.push(f(t(s(n(h.getImageData(2*d,2        
  *m,4,4).data),4)),c)),d+=1;o.width=i.width,o.height=i.height;for(var d=0        
 ,m=0,v=i.width*i.height/4,p=0;v&gt;p;p+=1)d&gt;2*Math.ceil(a.width/2)&amp;&amp;(d=0,m+=        
 1),console.log("Filling point ("+d+", "+m+") : "+e(l[p])),r.fillStyle=e(l        
 [p]),r.fillRect(2*d+1,2*m,2,1)  ,r.fillRect(2*d,2*m+1,4,2),r.fillRect(2*d        
+1,2*m+3,2,1),d+=1;u.result=o      .toDataURL("image/png"),u.resultCanvas         
=o,u.imageCanvas=i,u.image=a       ,u.done(),console.log(u.result)},a.one         
rror=function(t){console.log       ("The image failed to load. "+t)}}/*..         
............................       ......................................         
. ..........................       .....................................          
............................      ......................................          
.............................    .......................................          
.......................................................................           
.......................................................................           
..................  ..................................................            
................     .................................................            
..............       ................................................             
.............       ................................................              
...........        .................................................              
 .........         ................................................               
 .......          ................................................                
  ....           ................................................                 
                ................................................                  
                ...............................................                   
               ...............................................                    
              ..............................................                      
              .............................................                       
             ............................................                         
             ..........................................                           
              .......................................                             
              .....................................                               
               .................................                                  
                .............................                                     
                  ......................                                          
                                   .....                                          
                                  .....                                           
                                  .....                                           
                                  ....                                            
                                   */`
.replace(/\n/g,''))                                             


Usage:

Paint('DATA URI');


Fiddle.

The fiddle uses crossorigin.me so you don't need to worry about cross-origin-resource-sharing.

I've also updated the fiddle so you can adjust some values to produce the best-looking painting. Some pictures' colors might be off, to avoid this, adjust the accept_rate to adjust the algorithm. A lower number means better gradients, a higher number will result in sharper colors.



Here's the fiddle as a Stack-Snippet (NOT updated, in case the fiddle doesn't work):



/* Options */

var accept_rate = 82,  // 0 (low) - 100 (high)
    attempts    = 16, // Attemps before giving up
    edge_multi  = 2;   // Contrast, 2-4

function Paint(image_url) {
    var image = new Image(), canvas = document.createElement('canvas'), context = null, result = document.createElement('canvas'), resultContext = result.getContext('2d'), final_colors = [], self = this, color_choices = [
        [0,0,0],
        [255,255,255],
        [192,192,192],
        [128,128,128],
        [126,3,8],
        [252,13,27],
        [255,253,56],
        [128,127,23],
        [15,127,18],
        [41,253,46],
        [45,255,254],
        [17,128,127],
        [2,12,126],
        [11,36,251],
        [252,40,252],
        [127,15,126],
        [128,127,68],
        [255,253,136],
        [42,253,133],
        [4,64,64],
        [23,131,251],
        [133,255,254],
        [129,132,252],
        [6,66,126],
        [127,37,251],
        [127,64,13],
        [253,128,73],
        [252,22,129]
      ];
  image.crossOrigin = "";
  image.src = image_url;
  
  this.done = this.done || function () {};

  function hex(c) {
    var res = c.toString(16);
    return res.length == 1 ? "0" + res : res;
  }
  
  function colorHex(r) {
    return '#' + hex(r[0]) + hex(r[1]) + hex(r[2]);
  }
  
  image.onload = function () {
    canvas.width = image.width; canvas.height = image.height * 2;
    context = canvas.getContext('2d');
    context.drawImage(image, 0, 0, image.width, image.height);
    
    function averageColors(colors_ar) {
      var av_r = 0,
          av_g = 0,
          av_b = 0;
      
      colors_ar.forEach(function (color) {
        av_r += color[0];
        av_g += color[1];
        av_b += color[2];
      });
      
      return [av_r / colors_ar.length,
              av_g / colors_ar.length,
              av_b / colors_ar.length];
    }
    
    function arrayFrom(ar) {
      var newar = [];
      for (var i = 0; i &lt; ar.length; i += 1) {
        newar.push(ar[i]);
      }
      return newar;
    }
    
    function colorDif(c1,c2) {
      // Get's distance between two colors 0.0 - 1.0
      return (Math.abs(c1[0] - c2[0]) / 255 +
              Math.abs(c1[1] - c2[1]) / 255 +
              Math.abs(c1[2] - c2[2]) / 255) / 3;
    }
    
    var furthest = (function (cc) {
      // Determines furthest color
     
      // Reduces RGB into a "single value"
      reduce = cc.map(function(color) {
        return ( color[0] + color [1] + color [2] ) / 3;
      });
      
    }(color_choices));
      
    function intDif(i1,i2,t) {
        return Math.abs(i1 - i2) / t
    }
      
    function arrayIs(ar, int,d) {
        return intDif(ar[0],int,255) &lt;= d &amp;&amp;
               intDif(ar[1],int,255) &lt;= d &amp;&amp;
               intDif(ar[2],int,255) &lt;= d
    }
      
    function colorLoop(c1,c2) {
        var edgeCap =  edge_multi * ((accept_rate / 100) / 50), values = c2.map(function (i) {
            return colorDif(c1,i);
        });
        
        
        
      return arrayIs(c1,255,edgeCap)?[255,255,255]:
             arrayIs(c1,0,edgeCap)  ?[0,0,0]:
             c2[values.indexOf(Math.min.apply(Math, values))];
    }
       
    function colorFilter(c1, c2) {
      // Does the color stuff
      var rand  = Math.floor( Math.random() * c2.length ), // Random number
          color = c2[rand], // Random color
          randdif = colorDif(c1, color),
          threshhold = 1 - accept_rate / 100, // If the color passes a threshhold
          maxTries   = attempts, // To avoid infinite looping, 56 is the maximum tries to reach the threshold
          tries      = [];
        
        
      
      // Repeat until max iterations have been reached or color is close enough
        
      while ( tries.length &lt;= maxTries &amp;&amp; colorDif( c1, color ) &gt; threshhold ) {
        tries.push(color);
        color = c2[Math.floor(Math.random() * c2.length)]; // Tries again
        
        if (tries.length == maxTries) {
          // Used to hold color and location
          var refLayer = tries.map(function(guess) {
            return colorDif(c1, guess);
          });
          
          color = tries[refLayer.indexOf(Math.min.apply(Math, refLayer))];
            tries.push(color);
        }
        
      }
      
      var edgeCap =  edge_multi * ((accept_rate / 100) / 50), loop = colorLoop(c1, c2);
        
      return arrayIs(c1,255,edgeCap)?[255,255,255]:
             arrayIs(c1,0,edgeCap)  ?[0,0,0]:
             colorDif(c1,color)&lt;accept_rate?color:
             loop;
    }
    
    function chunk(ar, len) {
      var arrays = [];

      while (ar.length &gt; 0)
        arrays.push(ar.splice(0, len).slice(0, -1));
      
      return arrays;
    }
    
    var x = 0, y = 0, total = (canvas.width * canvas.height) / 4;
    
    for (var i = 0; i &lt; total; i += 1) {
      if (x &gt; (Math.ceil(image.width / 2) * 2)) {
        x = 0;
        y += 1;
      }
      
      final_colors.push( colorFilter( averageColors( chunk( arrayFrom(context.getImageData(x * 2, y * 2, 4, 4).data), 4 ) ), color_choices) );
      
      x += 1;
    }
    
    // Paint Image
    result.width = canvas.width;
    result.height = canvas.height;
    var x = 0, y = 0, total = (canvas.width * canvas.height) / 4;
    for (var i = 0; i &lt; total; i += 1) {
      if (x &gt; (Math.ceil(image.width / 2) * 2)) {
        x = 0;
        y += 1;
      }
      
        console.log("Filling point (" + x + ", " + y + ") : " + colorHex(final_colors[i]));
    
      resultContext.fillStyle = colorHex(final_colors[i]);
      resultContext.fillRect(x*2 + 1, y * 2, 2 , 1); // Top
      resultContext.fillRect(x * 2, y * 2 + 1, 4, 2); // Middle
      resultContext.fillRect(x * 2 + 1, y * 2 + 3, 2, 1); // Bottom
      
      x += 1;
    }
    
    self.result = result.toDataURL("image/png");
    self.resultCanvas = result;
    self.imageCanvas = canvas;
    self.image = image;
    self.done();
    
    console.log(self.result); 
    
  };
  
  image.onerror = function(error) {
    console.log("The image failed to load. " + error);
  }
  
}


// Demo

document.getElementById('go').onclick = function () {
    var url = document.getElementById('image').value;
    if (!url.indexOf('data:') == 0) {
        url = 'http://crossorigin.me/' + url;
    }
    var example = new Paint(url);
    
    example.done = function () {
        document.getElementById('result').src = example.result;
        document.getElementById('result').width = example.resultCanvas.width;
        document.getElementById('result').height = example.resultCanvas.height;
        window.paint = example;
    };
};
&lt;!--This might take a while--&gt;
Enter the image data URI or a URL, I've used crossorigin.me so it can  perform CORS requests to the image. If you're inputting a URL, be sure to include the http(s)
&lt;input id="image" placeholder="Image URI or URL"&gt;&lt;button id="go"&gt;Go&lt;/button&gt;
    &lt;hr/&gt;
    You can get the image URI from a website like &lt;a href="http://jpillora.com/base64-encoder/"&gt;this one&lt;/a&gt;
    &lt;hr/&gt;
    
    Result:
    &lt;img id="result"&gt;
        &lt;span id="error"&gt;&lt;/span&gt;&lt;hr/&gt;
        Check your console for any errors. After a second, you should see the colors that are being generated / printed getting outputted to the console.






To commemorate New Horizon's flyby of Pluto, I've inputted an image of Pluto:







For the following I've set it to make them resemble the original as close as possible:

I ran this with OS X Yosemite's default wallpaper. After leaving it run for a bit, the results are absolutely stunning. The original file was huge (26 MB) so I resized and compressed it:



The starry night (I've used a higher resolution image for better results)



A picture I found on google: