Which time-frequency coefficients does the Wavelet transform compute?
You are correct that the FWT is better thought of as a "cousin" of the STFT, rather than the FT.  In fact, the FWT is just a discrete sampling of the CWT (continuous wavelet transform), as the FFT/DFT is a discrete sampling of the Fourier transform.  This may seem like a subtle point, but it is relevant when choosing how you discretize the transform.

The CWT and STFT are both redundant analyses of a signal.  In other words, you have more "coefficients" (in the discrete case) than you need to fully represent a signal.  However, a Fourier transform (or say a wavelet transform using only one scale) integrate a signal from -infinity to +infinity.  This is not very useful on real world signals, so we truncate (i.e. window) the transforms to shorter lengths.  Windowing of a signal changes the transform -- you multiply by the window in time/space, so in transform space you have the convolution of the transform of the window with the transform of the signal.

In the case of the STFT, the windows are (usually) the same length (non-zero extent) at all time, and are frequency agnostic (you window a 10 Hz signal the same width as a 10 kHz signal).  So you get the rectangular grid spectrogram like you have drawn.

The CWT has this windowing built in by the fact that the wavelets get shorter (in time or space) as the scale decreases (like higher frequency).  Thus for higher frequencies, the effective window is shorter in duration, and you end up with a scaleogram that looks like what you have drawn for the FWT.

How you discretize the CWT is somewhat up to you, though I think there are minimum samplings in both shift and scale to fully represent a signal.  Typically (at least how I've used them), for lowest scale (highest frequency), you will sample at all shift locations (time/space).  As you get higher in scale (lower in frequency), you can sample less often.  The rationale is that low frequencies don't change that rapidly (think of a cymbal crash vs. a bass guitar -- the cymbal crash has very short transients, whereas the bass guitar would take longer to change).  In fact, at the shortest scale (assuming you sample at all shift locations), you have the full representation of a signal (you can reconstruct it using only the coefficients at this scale).  I'm not so sure about the rationale of sampling the scale.  I've seen this suggested as logarithmic, with (I think) closer spacing between shorter scales.  I think this is because the wavelets at longer scales have a broader Fourier transform (therefore they "pick up" more frequencies).

I admit I do not fully understand the FWT.  My hunch is that it is actually the minimum sampling in shift/scale, and is not a redundant representation.  But then I think you lose the ability to analyze (and mess with) a signal in short time without introducing unwanted artifacts.  I will read more about it and, if I learn anything useful, report back.  Hopefully others will like to comment.