Well, 2 million polys can be a lot, or a little, depending on the area you’re trying to paint over. It sounds like you’re aware that POlypaint is mesh resolution dependent, but I have no idea how big an area those polys are covering. It may be that you still need to increase your sub D another level for the best results.
As for Projection master, that is dependent on the image resolution of the applied texture, and in turn, how well distributed those pixels are over your UVs. You may need a larger texture, or you may need to adjust your UVs to allow more detail in larger areas.
If you are using PM without a texture and UV applied, as far as I know, any color is still simply being applied with the polypaint process, so subject to the same limitations, which would explain while it got as blurry as your polypaint situation when you dropped it.
Also be sure you are not viewing a zoomed in canvas. Click you canvas to “actual” size, or better yet, “half size” to see AA smoothing applied.
From my own experience, I have always considered poly-painting to be better for broader, more diffuse applications of color, while when I want the crispest and most precise results, say with a logo application, I have better luck with projection master and an applied texture of sufficient size.