Так что мне удалось сделать это, используя тип изображения "palette", но полученный файл не такой маленький, как я ожидал ... Вот мой код на случай, если он будет полезен для кого-то другого, или если кто-то может улучшить его.
from PIL import Image
im = Image.open("image1.png")
imP = im.convert('RGB').convert('P', palette=Image.ADAPTIVE, colors=3)
imP.putpalette([
0, 0, 0, # index 0 is black background
0, 0, 255, # index 1 is blue
255, 0, 0, # index 2 is red ])
im2 = Image.open("image2.png")
imP2L = im2.convert('L') # need a greyscale image to create a mask
mask = Image.eval(imP2L, lambda a: 255 if a == 0 else 0)
imP.paste(2, mask) # Paste the color of index 2 using image2 as a mask
imP.save('out3.png', transparency = 0, optimize = 1) # Save and set index 0 as transparent