Didn't Alien Breed 3D AGA use 4096 colours at the same time (using a Copper trick). It was blocky but was pretty fast. I think it mentions the details on the box. Beast is the best looking Classic Amiga game, especially if you play on monitor or scart TV.
Regards
-EDIT-
Banshee was another really nice looking game :-)
