There's only like an extra 25 dB of path loss to the moon than Earth since GPS satellites are at orbits of 20,000 km. Of course the GPS antennas are probably oriented facing the Earth, but you'd still see GPS satellies on the far side (with a bit more path loss). Since GPS has a 43 dB processing gain from the modulation scheme, and thermal noise levels on the moon are similar to Earth (I think?), that means you need -150 dBm or so at the receiver. I believe newer GPS satellites have an EIRP of 50 dBm or so, so receiving GPS signals on the moon might work without even using a high gain antenna. Use of a high gain antenna would probably completely compensate for the increased path loss to the moon.

Low lunar orbits are unfortunately too unstable.