Changing lots of colors in a shader efficiently for the general case is actually kind of hard.
The example you linked to is a pretty good idea, but it relies on point filtering and disabling compression on the textures. If I were going down a route similar to that I would probably just have all my sprites be grey scale using an Alpha8 format (uncompressed, but single channel, so about the same memory usage as a compressed texture) then map the grey scale values as indices into a palette texture.
A more common technique for recoloring stuff is using a mask texture, but since you only have 3 or 4 colors per mask you only get 4 or 5 (R, G, B, A, and nothing) regions you can control unless you use a second mask texture. If you want 10 colors that’s going to be difficult.
You could also do what color grading post processes effects do and use a 3D texture to map one color to any other color … but that’s probably overkill for what you want.
Honestly your alpha channel indexing is a fine idea. Even with a compressed texture you shouldn’t have a problem (though you will still need to use point sampling, and compression might still mess it up a little).
I suspect your shader looks something like this:
if (alpha < 16)
// transparent
else if (alpha >= 16 && alpha < 32)
// use color A
else if (alpha >= 32 && alpha < 48)
// use color B
… etc etc …
Don’t do that. Just have a texture that’s as many number of colors you want to be able to have control over wide, and 1 pixel high, set it to uncompressed, clamped wrap, no mip maps, and point filtering, then just do something like this:
fixed4 tintColor = tex2D(_PaletteTex, float2(alpha, 0));
Here’s a version of that little guy done in grey scale with a palette of 16 possible colors:

The palette you can download below. Set the hero texture to be uncompressed, alpha from greyscale, no mips, point filtering. You can set the texture’s platform override to be Alpha8 as well. Set the palette to uncompressed, no mips, point filtering. Then use this shader:
Shader "Unlit/AlphaToPaletteShader"
{
Properties
{
[NoScaleOffset] _MainTex ("Texture", 2D) = "white" {}
[NoScaleOffset] _PaletteTex ("Palette", 2D) = "white" {}
}
SubShader
{
Tags { "Queue"="AlphaTest" "RenderType"="TransparentCutout" "PreviewType"="Plane" }
LOD 100
Pass
{
CGPROGRAM
#pragma vertex vert
#pragma fragment frag
// make fog work
#pragma multi_compile_fog
#include "UnityCG.cginc"
struct appdata
{
float4 vertex : POSITION;
float2 uv : TEXCOORD0;
};
struct v2f
{
float2 uv : TEXCOORD0;
float4 vertex : SV_POSITION;
};
sampler2D _MainTex;
sampler2D _PaletteTex;
float4 _PaletteTex_TexelSize;
v2f vert (appdata v)
{
v2f o;
o.vertex = UnityObjectToClipPos(v.vertex);
o.uv = v.uv;
return o;
}
fixed4 frag (v2f i) : SV_Target
{
fixed alphaIndex = tex2D(_MainTex, i.uv).a;
float paletteU = (alphaIndex * _PaletteTex_TexelSize.z + 0.5) * _PaletteTex_TexelSize.x;
fixed4 col = tex2D(_PaletteTex, float2(paletteU, 0.0));
clip(col.a - 0.5);
return col;
}
ENDCG
}
}
}
