Why would I get electrocuted if I touched a non-isolated power line with my feet on the ground?
Electrocution can be a low current phenomena - milliamps across the heart can trigger ventricular fibrillation and death. If you're talking about mains voltage in the hundreds or thousands of volts, even a large resistance will allow enough current to flow to do damage.

Earth provides a path because there are points in the distribution network where parts of the network are tied to earth. These points are generally 'solidly' earthed with large conductors buried deeply, such that local environmental variation (rainfall, water table, etc.) don't appreciably affect the 'quality' of the earthing.

In your hypothetical situation of touching a conductor while touching earth, the path of least resistance will likely be from yourself to the nearest earth connection, then through that connection via the earth back to the generator. As Chris Stratton said in his comment, it will likely be very close by, and the connection through the earth between the solid earth points will be surprisingly low. The limiting factor will be the resistance between you and the nearest earthing point.

Consider the 'TN' earthing system:



Also, consider the 'TT' earthing system:



In both of these scenarios, there's a local earth reference at the generator. This allows both usage of the earth as a low-noise reference (for EMI filtering and other things) as well as allowing Earth to be a fault current path (allowing high enough current flow to trip an interrupting device like a fuse or a breaker.)

Your 'two side' scenario (touching the high side with one hand and the low side with the other) is worse, yes, since there isn't that limiting resistance between yourself and the local earthing point knocking some of the steam out of the hit. The absolute worst-case earthing situtation, though, may not actually be so different from a line-to-line hit - imagine it happening close to the generator, with the earthing point only a few meters
away.