I think this is more of a "Mercruiser" thread than a prop thread, probably get more responses over in the Mercruiser forum.
^^^ Agree with QC, I wouldn't expect much more than 35 with a 19.5'er - 3.0L combo. I have a heavily loaded 18.5' fishing rig with a 3.0L and can only squeak out 35MPH at 4600RPM,,, 18P 4 blade prop. Your sped sounds correct, so I wouldn't monkey with the prop at this point.
I'd check the tach as the RPM's don't sound correct. Is the speed by GPS or the boat's speedo, GPS is best.
For the bogging at 3000RPM and picking up again, and only going to 4000RPM,,, check to see if the distributor is advancing all the way. The dist curve should be all in by 3000RPM, but.... The weights and springs could be rusted and hanging, not allowing the dist to advance all the way,,,, if it's points....
Post up the engine serial number for better help.