classic suggestion would be outer space, but i guess the transitions aren't too challenging then (see actual hexquisite).. could mount into everybody pixeling his planet/spaceship/whatever surrounded by deep space black and some stray pixels as stars
i'd go for pirates.. think of the whole monkey island / pirates of the caribean feel.. skulls, ghostships.. parrots! =P
another thing that i had in mind is a developing palette.. like starting tiles have a given 4 color-palette, the bunch of tiles surrounding the start tile have one additional color and so on. might be a bit costly in terms of moderation though.
what also would be nice is a field separated into different areas (top 3 rows are sky etc.) or even into totally different themes.. the "theme transition tiles" would be quite interesting; think of the map of "lemmings - the tribes" (http://www.abandonia.com/files/games/272/Lemmings%202%20-%20The%20Tribes_3.png
), just with better transitions