Vertex painting is far too soft for me:
I'm looking to paint something more like this (not exact, but close enough):
Instead of smooth interpolation, color interpolation should be done on a per-face basis and not smoothed between faces. And if possible I would like to paint faces, not vertexes.