Let's use an example with a = 5, c = 7 and m = 16. x denotes the list of random element, x[0] is the first element, x[1] the second, x[2] the third, x[3] the fourth, etc. We start with x[0] = 0. Let's calculate x[1] now:
x[1] = (a*x[0] + c) mod m
x[1] = (5*0 + 7) mod 16
x[1] = 7

Now let's do x[2]:
x[2] = (a*x[1] + c) mod m
x[2] = (5*7 + 7) mod 16
x[2] = (42) mod 16
x[2] = 10

If you continue this you will get the semi-random list
0, 7, 10, 9, 4, 11, 14, 13, 8, 15, 2, 1, 12, 3, 6, 5, 0, ... (repeats as soon as it reaches the starting point again.)

To guarantee that you really get every value between 0 and m-1, you need to make sure of three important requirements:
1. m and c have to be relatively prime. This is pretty easy if you make sure that m is a power of 2 (2, 4, 8, 16, 32, 64, ...) and that c is odd. Done
2. a-1 is divisible by all prime factors of m. If m is a power of 2, you just need to make sure that a is odd and not 0.
3. If m is divisible by 4, then a-1 also has to be divisible by 4. If m is a power of 2, then it is nearly always divisible by 2 so you have to make sure that a is some value of the list {5, 9, 13, 17, 21, 25, ...}

m has to be the size of your map relative to the resolution of the spawn point algorithm. Let's say the map is from -128 to +128 (distance ~256) on both coordinates and we want to be able to spawn the player on every whole number. That means there are 256*256 = 65536 = 2^16 locations we can check for spawning - no problem with today's computing power and most of the time we get a valid position much sooner than that. If you want to spawn the player on a bigger map just multiply the random number with a scale factor. Therefore m is 65536.
For a and c you should just google some good values. I got a = 25173 and c = 13849 which results in
x[n] = (25173*x[n-1] + 13849) mod 65536;
(Depending on how Unity / C# handles integer sizes you can maybe use unsigned short and remove the mod operation.)
(To get values for x and z coordinates, split the random number into two halves, for example the first 8 bits and the last 8 bits. This will guarantee that every possible location is available.)

No solution without disadvantages.
LCGs are not good random number generators. Take a look at the example numbers 0, 7, 10, 9, 4, 11, ... - even, odd, even, odd, even, odd, ... That is the most glaring weakness of LCGs, but I think it is no problem for using them in this algorithm. The numbers always swap between even and odd for every check, but that only means the next position check can't be exactly next to the current one. It will still check every position Doesn't matter, right?