Davey, You cannot be sure that your "gain" problem centers around the gain of your phono stage (65db per your report) and the output of your cartridge (0.25mV). The subjective impression of gain also depends upon the input sensitivity and gain of your linestage (if you drive a linestage via your phono stage) and the input sensitivity of your amplifier(s), assuming other evidence that the amplifier/speaker match is copacetic. On paper, a cartridge with a real output of 0.25mV driving a phono stage with 65db of gain should be fine. I am currently using an Audio Technica ART7 (less than 0.2mV output) into a Manley Steelhead set at 65db for gain. The Manley output stage adds no further gain, and there is absolutely no sense of strain or noise due to stress. (The Manley drives a pair of Beveridge direct drive amplifiers which have a solid state input stage; I do not know the input sensitivity, but obviously it's adequate.)
By the way, for the purposes of discussion, at least, it's best to separate "distortion" from "noise", I think. Your lumping of noise and distortion is not wrong but maybe a little confusing. Noise of the kind you describe is accounted for by the "signal to noise ratio" specification, which is usually stated separately from harmonic or IM distortion measurements.