Aura DV (schwer zu bekommen), Dogwaffle, TVPaint (Amiga, läuft mit UAE), Gimp natürlich...

Theoretisch kann fast jedes Malprogramm Dithering, weil das beim Runterkonvertieren der Farbtiefe eine der naheliegenden möglichen Techniken ist (Näherungswerte als Farbflächen oder eben Dithering).

Was willst Du denn konkret machen? Weil, ist es nicht sinnvoller, die Bilder in einer höheren Farbtiefe zu erstellen und anschließend zu konvertieren? So mache ich üblicherweise Bilder mit reduzierter Palette (als 32bit angelegt, mit selektiver Palette gezeichnet, Gradienten und Ähnliches von Hand gezeichnet - sieht ohnehin sauberer aus, weil mathematisch richtig nicht unbedingt angenehm für's Auge sein muss). Nebenbei, wenn Du sagst, Du willst mit einer 256 Farben Palette arbeiten, meinst Du dann normale 8bit, oder eine selektive Palette?

PS: Ich benutze dafür allerdings keinen Gimp oder so, sondern das zu Unrecht völlig unbekannte Aura/ Mirage von TVPaint. Wird u.A. von Oscar-Preisträgern wie Paul Fierlinger benutzt, aber auch von Demo-Szene Gruppen wie Pulse, und die Community ist sehr klein aber extrem fein, freundlich und hilfreich - wo sonst bekommt man im offiziellen Forum direkt Hilfe vom Lead-Coder (Sebastien), dem Chef (Paul) oder einem Academy-Award Gewinner (noch ein Paul)? Das ist aber beileibe nicht kostenlos - aber immer noch billiger als der peinliche Photoshop-Murks... ;-) Deshalb, solltest Du keine Paar-Hundert Öhre springen lassen wollen, versuche, Aura DV zu organisieren. Was besseres für Umsonst ist eigentlich kaum zu bekommen. Wenn Du's irgendwo im Netz finden solltest, zieh's Dir einfach (DV jetzt, nicht das 'große' Aura - obwohl das die 400 Euro echt wert ist). Newtek, der damalige Vertrieb, hat's ohnehin verschenkt - konnte man bei allen Newtek Händlern kostenlos mitnehmen...