Isn't your problem more about Color quantization than about dithering? If you have big character cells like in a terminal dithering won't help you much. For each cell you want to find the best shaped cell and a foreground and background colour that are the closest to a colour from the supported palette.
But maybe I didn't understand your real problem yet
But maybe I didn't understand your real problem yet