If an observer changes their velocity, is it equivalent to a momentum shift? Suppose we have a world with one massive free particle and one observer. If the observer changes their velocity with respect to the particle, will this have the same effect on $\lvert\Psi(r,t)\rvert^2$ as if $\langle p\rangle$ was changed locally (for example, using compton scattering if we added another particle)?
Part of me says, yes: the "wavelength of $\Psi$" is related to momentum by the de Broglie relation, and momentum is relative (assuming we have just a Galilean transform here). 
Part of me says, no: due to the uncertainty principle, the probability of finding a free particle anywhere would seem to be uniform and negligible over all space. From this argument, the wave function shouldn't change, because for a free particle, it wouldn't have a well-defined wavelength to begin with.
I know I'm missing some conceptual connection, because these can't both be true.
I am currently studying an intro QM course, so please take my undergraduate level of understanding into account! 
 A: As other answers have mentioned, the SE is invariant under Galilean transformation, and there are other PSE posts that cover this. However, I wanted to address some specific things in your question.

Part of me says, no: due to the uncertainty principle, the probability of finding a free particle anywhere would seem to be uniform and negligible over all space. From this argument, the wave function shouldn't change, because for a free particle, it wouldn't have a well-defined wavelength to begin with.

First, a change in relative velocity will just change $\langle p\rangle$, not $\Delta p$, so we don't need to worry about any changes due to the uncertainty principle.
But also something to keep in mind is that systems with a certain Hamilton do not have to be eigenstates of that Hamiltonian. Yes, eigenstates of the free particle Hamiltonian have $\Delta p=0$ and are not physically valid states, but you can still have a free particle system that is in a superposition of such states so that $\Delta p\neq 0$. 
To use another example, think of the particle in a box. Eigenfunctions of the Hamiltonian take the form of standing sine waves, but that doesn't mean all particle in a box systems look like this. Your system can be a superposition of these states, and hence $\psi(x)$ will not be a sine wave nor an eigenfunction of the Hamiltonian. 
A: No $|\psi(x,t)|^2$ will not change. 
Reason Schrodinger equation is invariant under Galilean transformation. 
See this Galilean invariance of the Schrodinger equation 
A: The relation between the two cases is given by a unitary transformation. This means that $|\psi(x,t)|^2$ is necessarily preserved.
