So I figured out I can tune my G string just a little flat so all the frets sound in tune, except that, of course, leaves open G sounding like F#.
What should I do?
Check the intonation. The bridge/saddles may need moving, so that the 12th fret harmonic is exactly the same note as the fretted 12th. As an extra check, capo on 1st fret, and hear the 13th fret harmonic is the same as the fretted 13th.
Look at the nut. The string should make contact with the edge of the nut towards the fretboard. Here is a picture of what it should look like. You can fix it yourself or get it repaired at a luthier/guitar store.
If this is an electric guitar, it could be from using an unwound G. You could try a set of strings with a wound G string and see if that helps.
This seems to be a nut/string saddle issue. If you're sure all the fretted notes are in tune when you de tune the third string, then it means that your open G string is too long because the string is not contacting the edge of the nut. The act of fretting the notes is enough to press the string down onto the correct contact point on the nut. You can buy a pocket-sized folding set of mig welder tip cleaning files for a few dollars. Select the appropriate file and ever so gently (think microns here) slope the nut slot so that it falls away on the headstock side. String up and re test after every file stroke: you do not want to take the slot too deep. It's possible that the intonation at the bridge will require a tweak too, depending on how the guitar was 'originally' set up. If your guitar has a bone/plastic saddle do not use the mig tip cleaning files; they should only be used on slots. If your guitar has adjustable saddles remember any adjustment will be tiny.