Instead of using stickers, have you considering making a slot into each face, allowing a small square to be slotted into place? Then you could paint the squares separately with acrylic to achieve the same solid color, then slot it into place. It's alot more crafty and elegant then stickers. And by keeping each piece separate well painting, you don't have to put in alot of careful brush work. You could even use metallic or iridescent spray paints to give each square a nifty finish stickers can't match.
Alternatively, another idea might be to forgo the traditional simple colors and instead emboss the sides of the cube with famous paintings, faces, or some other kind of simple and recognizable picture. That way, instead of just colors, each face could be a work of art on to itself.
For example:
If you were making just a regular Rubix Cube, make a thin square box with a few thousand faces and use a function like 3D Studio's Displace to extrude the box. Then carefully divide the box into 9 even pieces, shrink a bit so there's a gap between each piece, and affix each piece to the face of one of Cube elements.
Or you could attach end caps to each piece, much the same way the
Gear Ball was made into the
Gear Heart.
You might remember the Darth Maul head that was also a Rubix Cube? You could attach sectioned geometry to each face, making a puzzle that is also a statue on to itself when completed.