...painters algorithm sounds quite wasteful to me...
Sort in reverse and use a c-buffer, and you have the same result without overdraw. I was mainly referring to the artifacts you're willing to allow. But considering the extremely low processor power I guess that's not really a problem.
So a c-buffer is probably going to be your best bet. For BSPs just render from front to back. For other geometry sort polygons front to back. Both can make use of the c-buffer so it's a pretty uniform way of rendering.
The c-buffer itself can be implemented either with spans (requires some basic memory management), or 1 bit per pixel (requires a fast way to count bits).