I've tried it. My results with K-means clustering of LAB or LCH colorspaces were 'best', but still not all that satisfactory.

Currently, HUSL seems like the best colorspace for attempting to programmatically derive a palette from. HSY is simpler but also less well optimized (in terms of maximizing difference between colors), though it is better than HSL.

I've tried YIQ and YCbCr, IMO they are better than RGB but otherwise fairly unremarkable.

I recommend entirely ignoring HSV: it is possibly the worst colorspace I've encountered in terms of providing meaningful measures of difference between colors.

Finally, if you're going to do what Gil suggests, keep in mind the algorithm you use for reduction. Most palette reducers use some kind of median cut, which generally reduces contrast by minimizing extreme values, so consider increasing contrast before reduction, to compensate.

It's more important to provide equally spaced components, because it's possible to increase number of values for one component and reduce it for others. 6-8-5 values in RGB with gamma correction is good. I said YIQ may be best because it's better for reducing values. YCbCr, for example, includes all luminance information in one component, allowing for reduction of other components. In RGB, every component has varying degrees of luminance information, making using reduction giving more loss in palette. Still, green includes most luminance information.

I respect that you're doing portraits at such a small size.
But consider the target market and where you're advertising: are you going to sell $1 pixel portraits, to pixel artists?
Second, by requiring an iOS app you restrict your market to mobile apple users only.
Finally, downloading an app is an unfamiliar barrier, where people are even less likely to trust you than if you just set up some sort of paypal system.

I agree. It would be better if it was available to android, windows, linux or mac users, not only mobile apple.
Also, it's probably not worth 1$ to have pixel art. In windows, linux and mac, just open paint. For android, download this: https://play.google.com/store/apps/details?id=net.spc.app.pixelarteditor
Now you can make pixel art.

Define "Best".

Go to school! I need people to know how many grays, how much extent these colors are needed, etc. and you don't know what is even best for general use!!!

If there was a best one, there would be no reason to use any other palette, right ?

In general, if you're striving to "compute" a versatile palette, you should rather try split the HSV / HSL spaces than the RGB cube. There are some very large areas of these cubes where you don't need a lot of detail, but they are more easy to describe/define/compute according to HSL : Ex. "the more saturation increases, the more hue is important" and "as the color approaches maximum and minimum lightness, hue and saturation become irrelevant"

I know about using HSL/HSV spaces instead. Anyway, thanks for a hint!

* Level combination: each of 4-16-4, 8-8-4, 6-6-6, 6-7-6, 6-8-5, 7-7-5, 5-9-5 and others for RGB are accepted.
* As above, but for hue, saturation, value/light. NES tried this.

YIQ color space may give best results.

I want to know what is best 256-color palette. Not all entries have to be occupied.
I know these:
* Subset of 10-10-10 level RGB (1000 colors). First 125 colors are combinations of 5 levels of RGB each with LSB off. Next 125 are same, but with LSB on. For total of 250 colors, 6 remain.
* Subset of 16-16-16 level RGB (4096 colors). The format is IIRRGGBB: R, G and B are two most significant bits of each component, while I sets 2 LSBs of each component.
* Another IIRRGGBB format palette, but I sets color brightness to 25, 50, 75 or 100 percent of original. There is more fidelity in darker colors, but there is some redundancy: blacks, and 66% red with 50% brightness is same as 33% red with 100% brightness.
* 256-level grayscale for full brightness fidelity but no color/saturation fidelity at all. Variant: 128-level grayscale and fill remaining 128 colors to compensate for human's limited vision (human sees 21-bit RGB, not 24-bit).
* Level combination: each of 4-16-4, 8-8-4, 6-6-6, 6-7-6, 6-8-5, 7-7-5, 5-9-5, 5-10-5 and others for RGB are accepted.
* As above, but for hue, saturation, value/light. NES tried this.
* 2 bits for red/blue, 3 bits for green. Other bit is LSB of red and blue.
* Make four cubes of 64 colors, where there are 4 RGB levels in each cube chosen from 8 levels. Example: 0-2-5-7, 0-1-2-3, 2-3-4-5, 4-5-6-7. Configurator link: http://drag.wootest.net/misc/8bit_rgb.html
* To reduce large RGB bit-based palette by 2 bits, merge LSB of red, green and blue to one bit, as long as they all exist. If there are only two normal components with their own bits, you can only merge them to compress by 1 bit. This preserves all grays of palette (only if there are equal bits of each component), but reduces hue/saturation fidelity.

Here are samples for some of them:
Uniform HSV selection: There are 15 hues, 2 saturations, 9 values in full saturation, 7 values in half saturation, 17 grays and some transparency.

Uniform RGB selection: There are 4 bits for each component, where 2 least significant bits are shared between components. As a result, there are 2 bits for each component and 2 least significant bits shared between components. There are 18 hues, 2 saturations and 16 values. Best case precision is 12 bits, while worst case precision is 6 bits.
Format: RRGGBBSS
In other words, it's 4 RGB cubes, where each RGB component can be any of following values:

• 0, 68, 136, 204
• 17, 85, 153, 221
• 34, 102, 170, 238
• 51, 119, 187, 255

Example: 255, 119, 51 (orange)