Generate a 1920 x 1080 graphic with 2,073,600 unique colours
Python - 660+ bytes
Incremental Version

Full Size: http://www.pictureshack.net/images/57626_all_colors.png (4.52MB)
This is an image based on a Julia Set fractal. Each color is added to the image incrementally, although there is a substantial amount of pre-calculation.

Luminosity Version

Full size: http://www.pictureshack.net/images/95389_all_colors4.png (5.24MB)
I've added an option to iterate each color by luminosity, rather than by index. This doesn't qualify as &quot;counting up&quot; from zero, but this seems to be a lax requirement. It's interesting that these two orderings expose completely different structures in the image. To use this, set the use_luminosity flag to True.

Source
Requires PIL.
Be warned: this will take several minutes to execute. Using PyPy with Pillow runs in about one fifth the time of CPython with PIL, so I would recommend that, if possible.
from PIL import Image, ImageDraw

use_luminosity = True

dim = (1920,1080)

img = Image.new('RGB', dim)
draw = ImageDraw.Draw(img)

xstart = -.776707
ystart = -.134663

a = []

xd = 1.6 / 8192 / dim[0]
yd = 0.9 / 8192 / dim[1]

for x in range(dim[0]):
  print x
  for y in range(dim[1]):
    z = d = complex(xstart + x*xd, ystart + y*yd)
    c = 0
    while abs(z) &lt; 2 and c &lt; 5000:
      z = z*z + d
      c += 1
    a += [(c, -abs(z), x, y)]

a = a[1:]
a.sort(reverse = True)

t = [(i&gt;&gt;16, 255&amp;i&gt;&gt;8, 255&amp;i) for i in range(1, dim[0]*dim[1])]
if use_luminosity:
  t.sort(key = lambda c: c[0]*3 + c[1]*10 + c[2], reverse = True)

r = 0
for c,d,x,y in a:
  draw.point((x,y), t[r])
  r += 1

img.show()

Edit: updated so that #000000 is at the upper-left, as specified.
Edit: added a flag to iterate colors by luminosity.
Edit: switched to native complex calculations, and integer luminosity weights, which are slightly faster.

Solutions I worked on before the primary criterion became popularity-contest
PHP - 161 bytes
&lt;?header('Content-type: image/bmp');
ob_start();
echo'BM'.pack('I5S2',0,0,26,12,70780800,1,24);
for(;$i=($i-256)%2073601;)echo pack('CS',~$i,~$i&gt;&gt;8);
ob_end_flush();

This is going for fastest output possible. No library is used, just a pre-computed header, and direct byte output. Runs in less than 2s on my comp. By incrementing by 256 rather than 1, it produces a pseudo-gradient effect, with no real computation needed. The only downfall is that (0, 0) is not black, but the result looks a lot nicer.
ob_start(); and ob_end_flush(); aren't strictly necessary, but buffering the output makes it run a lot faster.

Other interesting increments include:
17: http://i.stack.imgur.com/ieyyZ.png
103: http://i.stack.imgur.com/WD2wa.png
326: http://i.stack.imgur.com/c4DSF.png
557: http://i.stack.imgur.com/eTTWE.png
943: http://i.stack.imgur.com/7rrmR.png
2125: http://i.stack.imgur.com/Ct1kM.png
And many others. Although, most patterns that look like anything resemble stripes of some sort

PHP - 105 bytes
&lt;?=BM.pack(I5S2,header('Content-type:'),0,26,12,70780800,1,24);
for(;$i&lt;2073600;)echo pack(CS,$i,$i++&gt;&gt;8);

Reckless disregard version.

Given a broken Content-type header, Chrome will do its best to figure out what it was sent. In this case, it correctly identifies it as image/bmp. The lastest versions of FireFox and IE are also able to fix the broken header.
The barewords BM, I5S2, and CS will generate a NOTICE error. To prevent corruption of the image, error reporting in php.ini will need to be set to prevent this (e.g. error_reporting = E_ALL &amp; ~E_NOTICE).
No output buffering. The image is constructed 3 bytes at a time, which is noticeably slower.
The point (0, 0) is considered to be the lower left, rather than upper left.



PHP-CLI - 83 bytes
&lt;?=BM.pack(I5S2,0,0,26,12,70780800,1,24);
for(;$i&lt;2073600;)echo pack(CS,$i,$i++&gt;&gt;8);

Run directly from the command line and piped to a file (e.g. $ php all-colors.php &gt; out.bmp), no Content-type header is necessary. The resulting file is identical to the 105 byte version, and can be viewed in Chrome.