I think color theory alone isn't enough to produce good color palettes. eg. try going to https://color.adobe.com and choose one of the color rules, then go to https://color.adobe.com/explore and compare with user-contributed palettes. There's a huge difference imo.
As for why a GAN specifically, I talk a bit about that in one of the blog posts. Neural nets trained with L1/L2 loss tend to produce "averaged" colors, dull greys and browns. The learned loss from a GAN allows the output to take on more extreme values.
You could solve the averaging problem by applying the L1/L2 trained net to exponential color gradients rather than linear ones. By doing so you are telling the NN that humans care about exponential changes in color because that's how our eyes work. E.g. we notice if you double the amount of green but probably not if you just increment it.
I think there are rather simple solutions to these types of problems. But sometimes everything looks like a nail.
GANs are good at generating plausible images given a set of examples, which is exactly what we're doing here.
A statistical approach might work, but you'd be essentially interpolating your existing samples. A GAN is capable of generating novel solutions.
The crux of the issue is that despite just having 5 colors, the solution space is huge (256^15), and most of the search space is junk. The difficult part is identifying what looks good, and classically this is just called color theory. The problem is that color theory is a leaky abstraction that doesn't capture what intuitively "looks good" and is largely used as a starting point for ideas rather than something that gives useable palettes. Hence the popularity of user-submitted and curated sites like coolors and the old kuler site.
You are right that 256^15 is a large search space. This number implies a 24bit color scheme.
(2^24)^5 = 256^15
Many of the colors in the 2^24 range are similar which is why most of the linear search space is boring. Our eyes don't care much about #f67368 vs #f67468 but we do care about #f67368 vs #f6e668. Why?
0x73 x 2 = 0xe6
Instead of blindly incrementing RGB color values, look at colors which differ by powers of 2. For example, choose 15 random values between 0 and 8. Let's call them c0 to c14. Then assign those numbers to your color pallet as 8-bit RGB values as follows.
Rounding 2^8 down to 255. You will find non-boring color schemes because the search space better fits how our eyes see color. This new search space is only 9^15 which is just less than 2^48, far less than 2^120 and a lot more interesting.
You could also search the HSV color space in this way and you don't have to only look at powers of two. Consider for, example powers of 1.25. The point is that by organizing your search, you will find interesting colors pallets easily.
I'm betting that your GANs already encode some sort of exponential search based on how you trained them vs your initial attempt using L1/L2.
As for why a GAN specifically, I talk a bit about that in one of the blog posts. Neural nets trained with L1/L2 loss tend to produce "averaged" colors, dull greys and browns. The learned loss from a GAN allows the output to take on more extreme values.