Are these most recent machines really incrementing the nonce? Is there an advantage over randomly picking them?

There's no advantage in selecting them "randomly", the resulting hash is always random. If there was a benefit in some sort of incrementing method, the entire system would be broken. They do some optimisation with the way the hash is calculated in some cases, but that's about it. The current processors are so fast that they can increment through the entire 32bit nonce space in under a second.

I suppose with an incrementing system, you could doll out the search space more efficiently. I imagine the more hash power you have, the more likely any two engines could randomly try the same nonce. (Assuming they were working off identical blocks). But it could be that there's a relationship between the way difficulty ratchets that keep the chances of testing the same nonces twice somewhat constant relative to the chance of finding a block.

Even if you're working on the same block, it's never the same work for the processor, the timestamp, order of transactions, number of transactions, and the coinbase all make the work unique.

i imagine n+1 is much faster than generating a large random number for each hash.

They probably generate a guid and then append a number and increment

Whats the advantage of using a new random number each time?

Fun EE fact: An LFSR is cheaper than a counter.

But an LFSR only gives you a pseudorandom result, right? I mean, I'd rather load thermal noise than use a shift.

For searching a 32-bit nonce space I'd rather use a PRNG than a true RNG to avoid wasting work due to birthday paradox collisions.