Return to Answer

By the way, you can get a 2048x2048 solution by changing only three constants: segment_length 136->204, k 6->11, n 1024->2048. This still uses only 1/4 of the available colors, and to exceed 1/2 you will need deeper changes than changing constants.

The reason for the 1/2 barrier is that this method uses twice the color density near creases of the second fold than at less interesting parts of the image.

Here's the python code, including tests and image creation. I think it displays the transpose of the image pasted into this answer. The logic is not so complicated; basically you fold the image like a map to fit into the rgb color box.

from itertools import islice
import numpy as np
import Image

def first_fold():
    r"""

          x       x
         / \     / \
    x   x   x   x   x
    |   |   |   |   |
    x   x   x   x   x
    |   |   |   |   |
    .   .   .   .   .
    .   .   .   .   .
    .   .   .   .   .
    |   |   |   |   |
    x   x   x   x   x
    |   |   |   |   |
    x   x   x   x   x
     \ /     \ /
      x       x

    """
    segment_length = 204
    q = 0

    while True:
        for i in range(segment_length):
            yield q, 1 + i
        q += 1

        yield q, 1 + segment_length
        q += 1

        for i in range(segment_length):
            yield q, segment_length - i
        q += 1

        yield q, 0
        q += 1


def second_fold():
    """

          aabbccddeeff
         a bacbdcedfe f
        a b cadbecfd e f
       a b c daebfc d e f
      a b c d eafb c d e f
     a b c d e fa b c d e f
    a b c d e f  a b c d e f

    """
    segment_length = 136
    k = 6
    q = 0

    while True:
        for i in range(segment_length):
            yield q, k + i
        q += 1

        for i in range(k):
            yield q + i, k + segment_length + i
        q += k
        for i in range(k):
            yield q + i, k + segment_length + (k-1) - i
        q += k

        for i in range(segment_length):
            yield q, k + segment_length - 1 - i
        q += 1

        for i in range(k):
            yield q + i, (k - 1) - i
        q += k
        for i in range(k):
            yield q + i, i
        q += k


def good_image(image):
    arr = np.asarray(image)
    n = arr.shape[0]
    if arr.shape != (n, n, 3):
        return False
    colors = set(tuple(x) for x in arr.reshape(n*n, 3))
    if len(colors) != n*n:
        return False
    if (arr < 0).any():
        return False
    if (arr > 255).any():
        return False
    e = np.abs(arr[1:, :, :] - arr[:-1, :, :])
    if (e > 1).any():
        return False
    e = np.abs(arr[:, 1:, :] - arr[:, :-1, :])
    if (e > 1).any():
        return False
    return True

def bad_image(image):
    return not good_image(image)

def main():

    assert(good_image([
        [[1, 1, 1], [1, 2, 1]],
        [[1, 1, 2], [2, 2, 2]]]))

    assert(good_image([
        [[0, 0, 0], [0, 1, 0]],
        [[0, 0, 1], [1, 1, 1]]]))

    assert(good_image([
        [[2, 20, 200], [1, 19, 199]],
        [[1, 19, 200], [2, 19, 200]]]))

    assert(bad_image([
        [[1, 1, 1], [1, 2, 1]],
        [[1, 2, 1], [2, 2, 2]]]))

    assert(bad_image([
        [[0, 0, 0], [0, -1, 0]],
        [[0, 0, -1], [-1, -1, -1]]]))

    assert(bad_image([
        [[255, 255, 255], [255, 256, 255]],
        [[255, 255, 256], [256, 256, 256]]]))

    assert(bad_image([
        [[2, 20, 200], [1, 19, 199]],
        [[1, 19, 200], [2, 19, 201]]]))

    assert(bad_image([
        [[2, 20, 200], [1, 19, 200]],
        [[1, 19, 199], [2, 19, 201]]]))

    n = 1024
    arr = np.zeros((n, n, 3), dtype=int)
    for u, (q, x) in islice(enumerate(first_fold()), n):
        for v, (a, b) in islice(enumerate(second_fold()), n):
            y = q + a
            z = b
            arr[u, v, :] = (x, y, z)

    assert(good_image(arr))

    img = Image.fromarray(arr.astype(np.uint8))
    img.show()


main()