I wasn't actually sure how to create 15- or 18-bit colors, so I just left off the least significant bit of each channel's byte to make 2^18 different 24-bit colors. Most of the noise is removed by sorting, but effective noise removal looks like it would require comparison of more than just two elements at a time the way Comparator does. I'll try manipulation using larger kernels, but in the mean time, this is about the best I've been able to do.

import java.awt.*;
import java.awt.image.*;
import javax.swing.*;
import java.util.*;

public class ColorSpan extends JFrame{
    private int h, w = h = 512;
    private BufferedImage image = 
            new BufferedImage(w,h,BufferedImage.TYPE_INT_RGB);
    private WritableRaster raster = image.getRaster();
    private DataBufferInt dbInt = (DataBufferInt) 
            (raster.getDataBuffer());
    private int[] data = dbInt.getData();
    
    private JLabel imageLabel = new JLabel(new ImageIcon(image));
    private JPanel bordered = new JPanel(new BorderLayout());
    
    
    public <T> void transpose(ArrayList<T> objects){
        for(int i = 0; i < w; i++){
            for(int j = 0; j < i; j++){
                Collections.swap(objects,i+j*w,j+i*h);
            }
        }
    }
    
    public <T> void sortByLine(ArrayList<T> objects, Comparator<T> comp){
        for(int i = 0; i < h; i++){
            Collections.sort(objects.subList(i*w, (i+1)*w), comp);
        }
    }
    
    public void init(){
        ArrayList<Integer> colors = new ArrayList<Integer>();
        for(int i = 0, max = 1<<18; i < max; i++){
            int r = i>>12, g = (i>>6)&63, b = i&63;
            colors.add(((r<<16)+(g<<8)+b)<<2);
        }
        
        Comparator<Integer> comp1 = new Comparator<Integer>(){
            public int compare(Integer left, Integer right){
                int a = left.intValue(), b = right.intValue();
                
                int rA = a>>16, rB = b>>16,
                    gA = (a>>8)&255, gB = (b>>8)&255;
                /*double thA = Math.acos(gA*2d/255-1),
                        thB = Math.acos(gB*2d/255-1);*/
                double thA = Math.atan2(rA/255d-.5,gA/255d-.5),
                        thB = Math.atan2(rB/255d-.5,gB/255d-.5);
                return -Double.compare(thA,thB);
            }
        }, comp2 = new Comparator<Integer>(){
            public int compare(Integer left, Integer right){
                int a = left.intValue(), b = right.intValue();
                
                int rA = a>>16, rB = b>>16,
                    gA = (a>>8)&255, gB = (b>>8)&255,
                    bA = a&255, bB = b&255;
                double dA = Math.hypot(gA-rA,bA-rA),
                        dB = Math.hypot(gB-rB,bB-rB);
                return Double.compare(dA,dB);
            }
        }, comp3 = new Comparator<Integer>(){
            public int compare(Integer left, Integer right){
                int a = left.intValue(), b = right.intValue();
                
                int rA = a>>16, rB = b>>16,
                    gA = (a>>8)&255, gB = (b>>8)&255,
                    bA = a&255, bB = b&255;
        
                    return Integer.compare(rA+gA+bA,rB+gB+bB);
            }
        };
        
        /* Start: Image 1 */
        Collections.sort(colors, comp2);
        transpose(colors);
        sortByLine(colors,comp2);
        transpose(colors);
        sortByLine(colors,comp1);
        transpose(colors);
        sortByLine(colors,comp2);
        sortByLine(colors,comp3);
        /* End: Image 1 */
        
        /* Start: Image 2 */
        Collections.sort(colors, comp1);
        sortByLine(colors,comp2);
        
        transpose(colors);
        sortByLine(colors,comp2);
        transpose(colors);
        sortByLine(colors,comp1);
        transpose(colors);
        sortByLine(colors,comp1);
        /* End: Image 2 */
        
        int index = 0;
        for(Integer color : colors){
            int cInt = color.intValue();
            data[index] = cInt;
            index++;
        }
        
    }
    
    public ColorSpan(){
        super("512x512 Unique Colors");
        setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        init();
        
        bordered.setBorder(BorderFactory.createEmptyBorder(2,2,2,2));
        bordered.add(imageLabel,BorderLayout.CENTER);
        add(bordered,BorderLayout.CENTER);
        pack();
        
    }
    
    public static void main(String[] args){
        new ColorSpan().setVisible(true);
    }
}