The boiling point is not identical to the temperature at which a material boils. Unless, of course, you define it that way. I don't know what your technical background it, so I'll mention a couple of basics which you can easily find out more about using widely available on-line resources.
The first point I'll make is that significant figures matter. The correct technical interpretation of your claim about the BP of water at 1 atm is that you meant 1.0 ± 0.5 atm. This is, of course an enormous range of atmospheric pressures. So, while the technical interpretation is clear, you probably didn't intend it. (See Wikipedia for both a discussion of significant figures and for one on atmospheric pressure (range).) The statement that water (assumed to be substantially pure and free of trace contaminants) boils at 100 °C at 1 atm is correct. The statement that the boiling point of water at 1 atm is 100 °C is also correct. Hence, to the accuracy of the values provided, there is no discrepancy.
As an aside, I am impressed that you understand the nucleation of vapor bubbles; I don't. Also, I've experienced (unfortunately) the explosive boiling of a cup of water I placed in a microwave oven. I don't recall its purity. After the heating cycle was complete, I opened the door and apparently the vibrations from that was enough to allow enough of the superheated (liquid) water to vaporize to blow most of the water out of the cup. Not an experience I recommend.
The point here is that while the equilibrium vapor pressure = gas phase (overhead) pressure is the criteria for the definition of boiling point, it just isn't true that water always boils at that temperature (and pressure).
There are two effects that are generally ignored when discussing (thermodynamic) boiling points: surface tension and isotopic composition. Not all water has the same isotopic composition, this fact is used in the study of a variety of historical, geological, and biological data. Surface tension can also be significantly affected by small trace contamination which are often quite difficult to remove. Other important factors are the height of the water column (assuming heating is from below), mixing of the liquid (rarely will you see isothermal samples of water, on a macroscopic scale), and even the composition of the gas phase (it is the Free Energy which determines the equilibrium; N2, O2, Ar, and CO2 all have different energies of interaction with H2O.) Surface tension is important in bubble formation. Small bubbles are especially sensitive to its value. As surface curvature flattens (radius gets bigger), surface tension becomes much less of a factor in the growth of bubbles. Vienna Standard Mean Ocean Water is the 'standard' water typically used in discussions of water's BP. (It is a pure water (not salt water) with a specified isotopic composition.) Depending on which temperature scale is used, at 1.00 atm water's BP is 99.99 °C.
The question of when and where bubbles nucleate and how fast they grow depends on convection, heating rate, water column pressure, the liquid's vessel's interior surface (both roughness and composition), and the purity of the water, both inorganic and organic contaminants, as well as dissolved gasses and particulates present. You are correct that in order to form a small bubble (here, small means on the order of 10 to 100 microns) surface energy (surface tension) requires a temperature and pressure higher than the equilibrium over the (flat) surface. Once bubbles attain sizes of 100 microns or so, the decrease in surface energy as the bubbles continue to grow is negligible. (Growth scales with surface area which scales at r², which is why large bubbles form preferentially to the same volume of small bubbles.) You can look at this as work, in the thermodynamic sense, as long as you realize that thermodynamics was long established before the atomic theory of matter (and before quantum mechanics). The two views, looking at the thermodynamics (energy and entropy) and looking at the molecular forces involved, are separate and complimentary perspectives. It's simplest not to mix them. From the simple equilibrium thermodynamic point of view, the process of boiling violates the assumption of "near equilibrium". That is, we need to be very careful about using thermodynamics in the discussion of bubble formation. All this is background to my last statement on the subject. Water boils near enough to 100 °C at 1 atm, given the typical ranges of composition, air pressure, temperature calibration, heating, vessel, etc.etc., to make it a piece of useful information.