I'm another one using FBlit on AGA/Indivison and finds that 256 colours is too slow and memory consuming. 64 colours is optimum for me on OS3.9. There is no colour benefit to Newicons if you increase to 128 colours it seems also.
Add PeterK's icon.library and it will be faster. Newicons i thought were 32 colors?