So if I replace my 1 MOhm resistor with, say, a 2 MOhm resistor I will increase its sensitivity (double?).
The sensitivity will probably increase, but not as much as double. There is a law of diminishing returns.
Will that also protect the Arduino better or the higher the parallel resistor the more the need for the 100 KOhm resistor in series?
A parallel resistor as high as 1M gives he Arduino little protection. If you hit the piezo with a hammer, maybe you will damage the Arduino, but it's unlikely otherwise.
And, on a related topic, if a piezo is not ideal for detecting, actually measuring, breath velocity, what other sensor would you recommend?
Do you mean detecting a person breathing lightly, or a blowing hard through a tube? For the former, perhaps a sensitive strain gauge would work better. For the latter, I suggest a turbine attached to a rotation sensor.