I think NunoSempere's answer is good and looking vNM utility should give you a clearer idea of where people are coming from in these discussions. I would also recommend the Stanford Encyclopedia of Philosophy's article on expected utility theory. https://plato.stanford.edu/entries/rationality-normative-utility/

You make an important and often overlooked point about the Long-Run Arguments for expected utility theory (described in the article above). You might find Christian Tarsney's paper, Exceeding Expectations, interesting and relevant. https://globalprioritiesinstitute.org/christian-tarsney-exceeding-expectations-stochastic-dominance-as-a-general-decision-theory/

On 3, this is a super hard practical difficulty that doesn't have a satisfactory answer in many cases. Very relevant is Hilary Greaves' Cluelessness. https://issuu.com/aristotelian.society/docs/greaves

As NunoSempere suggests, GiveWell is a good place to look for some tricky comparisons. My colleague, Stephen Clare, and I made this (very primitive!) attempt to compare saving human lives with sparing chickens from factory farms, which you might find interesting. https://forum.effectivealtruism.org/posts/ahr8k42ZMTvTmTdwm/how-good-is-the-humane-league-compared-to-the-against

1 & 2 might be normally be answered by the Von Neumann–Morgenstern utility theorem*

In the case you mentioned, you can try to calculate the impact of an education throughout the beneficiaries' lives. In this case, I'd expect it to mostly be an increase in future wages, but also some other positive externalities. Then you look at  the willingness to trade time for money, or the willingness to trade years of life for money, or the goodness and badness of life at different earning levels, and you come up with a (very uncertain) comparison.

If you want to look at an example of this, you might want to look at GiveWell's evaluations in general, or at their evaluation of deworming charities in particular.

I hope that's enough to point you to some directions which might answer your questions.

* But e.g., for negative utilitarians, axiom's 3 and 3' wouldn't apply in general (because they prefer to avoid suffering infinitely more than promoting happiness, i.e. consider L=some suffering, M=non-existence, N=some happiness) but they would still apply for the particular case where they're trading-off between different quantities of suffering. In any case, even if negative utilitarians would represent the world with two points (total suffering, total happiness), they still have a way of comparing between possible worlds (choose the one with the least suffering, then the one with the most happiness if suffering is equal).

Here is one answer to one part of your question.

Naively (?), I'd say that if you invest your resources in an action with a 1 in a million chance of saving a billion lives, and a 999,999 in a million chance of having no effect, then (the overwhelming majority of the time) you haven't done anything at all.

I think the idea you are getting at here is you'd rather have a 10% chance of saving 10 people than a 1/million chance of saving a billion lives. I can definitely see why you would feel this way (and there are prudential reasons for it - e.g. worrying about being tricked), but if you were sure this was actually the maths, I think you should definitely go for the 1/million shot of saving the billion.

To see why, imagine yourself in the shoes of one of the 1,000,000,010 people whose lives are at risk in this scenario. If you go for the 'safe' option, you have a 10%*1/1,000,000,010 ~= one in a billion chance of being saved. In contrast, if you go for the 'riskier' option, you actually have a one in a million chance - over a thousand times better!

I won't try to answer your three numbered points since they are more than a bit outside my wheelhouse + other people have already started to address them, but I will mention a few things about your preface to that (e.g., Pascal's mugging).
I was a bit surprised to not see a mention of the so-called Petersburg Paradox, since that posed the most longstanding challenge to my understanding of expected value. The major takeaways I've had for dealing with both the Petersburg Paradox and Pascal's mugging (more specifically, "why is it that this supposedly accurate decision theory rule seems to lead me to make a clearly bad decision?") are somewhat-interrelated and are as follows:
1. Non-linear valuation/utility: money should not be assumed to linearly translate to utility, meaning that as your numerical winnings reach massive numbers you typically will see massive drops in marginal utility. This by itself should mostly address the issue with the lottery choice you mentioned: the "expected payoff/winnings" (in currency terms) is almost meaningless because it totally fails to reflect the expected value, which is probably miniscule/negative since getting $100 trillion likely does not make you that much happier than getting $1 trillion (for numerical illustration, let's suppose 1000 utils vs. 995u), which itself likely is only slightly better than winning $100 billion (say, 950u) ... and so on whereas it costs you 40 years if you don't win (let's suppose that's like -100u).
2. Bounded bankrolling: with things like the Petersburg Paradox, my understanding is that the longer you play, the higher your average payoff tends to be. However, that might still be -$99 by the time you go bankrupt and literally starve to death, after which point you no longer can play.
3. Bounded payoff: in reality, you would expect that payoffs to be limited to some reasonable, finite amount. If we suppose that they are for whatever reason not limited, then that essentially "breaks the barrier" for other outcomes, which are the next point:
4. Countervailing cases: This is really crucial for bringing things together, yet I feel like it is consistently underappreciated. Take for example classic Pascal's mugging-type situations, like "A strange-looking man in a suit walks up to you and says that he will warp up to his spaceship and detonate a super-mega nuke that will eradicate all life on earth if and only if you do not give him $50 (which you have in your wallet), but he will give you $3^^^3 tomorrow if and only if you give him $50." We could technically/formally suppose the chance he is being honest is nonzero (e.g., 0.0000000001%), but still abide by rational expectation theory if you suppose that there are indistinguishably likely cases that cause the opposite expected value -- for example, the possibility that he is telling you the exact opposite of what he will do if you give him the money (for comparison, see the philosopher God response to Pascal's wager), or the possibility that the "true" mega-punisher/rewarder is actually just a block down the street and if you give your money to this random lunatic you won't have the $50 to give to the true one (for comparison, see the "other religions" response to the narrow/Christianity-specific Pascal's wager). Ultimately, this is the concept of fighting (imaginary) fire with (imaginary) fire, occasionally shows up in realms like competitive policy debate (where people make absurd arguments about how some random policy may lead to extinction), and is a major reason why I have a probability-trimming heuristic for these kinds of situations/hypotheticals.

Hey Ben, I think these are pretty reasonable questions and do not make you look stupid.

On Pascal's mugging in particular, I would consider this somewhat informal answer: https://nintil.com/pascals-mugging/ Though honestly, I don't find this super satisfactory, and it is something and still bugs me.

Having said that, I don't think this line of reasoning is necessary for answering your more practical questions 1-3.

Utilitarianism (and Effective Altruism) don't require that there's some specific metaphysical construct that is numerical and corresponds to human happiness. The utilitarian claim is just that some degree of quantification is, in principle, possible. The EA claim is that attempting to carry out this quantification leads to good outcomes, even if it's not an exact science.

GiveWell painstakingly compiles cost-effectiveness estimates numerical, but goes on to state that they don't view these as being "literally true". These estimates still end up being useful for comparing one charity relative to another. You can read more about this thinking here: https://blog.givewell.org/2017/06/01/how-givewell-uses-cost-effectiveness-analyses/

In practice, GiveWell makes all sorts of tradeoffs to attempt to compare goods like "improving education", "lives saved" or "increasing income". Sometimes this involves directly asking the targeted populations about their preferences. You can read more about their approach here: https://www.givewell.org/how-we-work/our-criteria/cost-effectiveness/2019-moral-weights-research

Finally, in the case of existential-risk, it's often not necessary to make these kinds of specific calculations at all. By one estimate, the Earth alone could support something like 10^16 human lives, and the universe could support somewhere something like 10^34 human life-years, or up to 10^56 "cybernetic human life-years". This is all very speculative, but the potential gains are so large that it doesn't matter if we're off by 40%, or 40x. https://en.wikipedia.org/wiki/Human_extinction#Ethics

Returning to the original point, you might ask if work on x-risk is then a case of Pascal's Mugging? Toby Ord gives the odds of human extinction in the next century at around 1/6. That's a pretty huge chance. We're much less confident what the odds are of EA preventing this risk, but it seems reasonable to think that it's some normal number. I.e. much higher than 10^-10. In that case, EA has huge expected value. Of course that might all seem like fuzzy reasoning, but I think there's a pretty good case to be made that our odds are not astronomically low. You can see one version of this argument here: https://slatestarcodex.com/2015/08/12/stop-adding-zeroes/

The problem is real. Though for 'normal' low probabilities I suggest biting the bullet. A practical example is the question of whether to found a company. If you found a startup you will probably fail and make very little or no money. However, right now a majority of effective altruist funding comes from Facebook co-founder Dustin Moskovich. The tails are very thick. 

If you have a high-risk plan with a sufficiently large reward I suggest going for it even if you are overwhelming likely to fail. Taking the risk is the most altruistic thing you can do. Most effective altruists are unwilling to take on the personal risk.