I understand Vertex paint uses VERTICES, but where there are smooth faces (and lack of vertices) am I just SOL?
At the risk of telling you what you know already..
'Vertex Colors' are stored in layers on the geometry, of (vertex-per-face) Face Corners. In 3.2+, they are looking to become 'Color Attributes', which could also be stored on vertices, shared by faces.
When you're Vertex Painting, you're storing color-data on those points. There is no more information than that available to shaders, which must linearly interpolate between the colours found on them. So, no, you can't paint half a face. Resolution is limited by the density of your geometry.
However, if you're Texture Painting, into a separately stored UV-mapped image, then shaders are interpolating between the UV coordinates found on the points, and can return the color found at the interpolated point in the image.
The texture-painting interface in Blender allows you to paint directly onto mapped geometry. It gives many options for defining brushes, their behaviour, masking.. etc. It's a little learning-curve all of its own. Typically you would set the object up with a material that expresses the image in one channel or another, and paint while watching the effect in Material Preview.
(Left, image.. Right, resulting material )