Paradigm does a good job of providing decent specs on the product pages. One thing to look for is the "Frequency response (on axis)" line on the Specifications page for each speaker. The 15B has a Frequency Response of "±2dB from 57 Hz - 20 kHz". This means that the speaker has relatively flat frequency response to about 57Hz at the same SPL (Sound Pressure Level - ie: "volume"). This means that it should be able to play a 57Hz note just as loudly and as clearly as a 15,000Hz note. Due to the speaker design (bass-reflex, meaning that the cabinet is ported) it has a specific tuning frequency (say, 55Hz). Bass extension and SPL fall off drastically below this tuning frequency; it's simply part of the design of the speaker. All this means that the 15B can be integrated into a HT with an 80Hz crossover to the subs with zero difficulties.
The Millenia 20, has a frequency response of "±2 dB from 110 Hz - 20 kHz". This is a perfect example of Hoffman's Iron Law: "You can have a small size, deep bass extension, or high sensitivity. Pick two". The M20 has 92dB/W/m sensitivity (pretty darned good for a home speaker, and even more so for an on-wall one), and is relatively thin and small compared to a tower speaker with the same driver layout. What it gives up is the bass extension.
The bass will roll off from 110Hz down quickly. It's usually advisable to cross over the speakers about 20Hz higher than the "F3" or lowest extension in the specs (Paradigm uses a tighter window than most, with a 4dB total variation rather than a 6dB one). Normally, this would mean that the Millenia 20 should be crossed over at 130Hz. The thing is, bass starts to become localized shortly above 80Hz. Deep male voices (ie: Darth Vader) average around 85Hz. With speakers that cannot be crossed over at 80Hz, you may end up with deep voices coming from the sub, which may NOT be placed right next to the speaker being used at that moment. Therefore, instead of Vader's voice coming from your left shoulder, it will be coming from wherever the subwoofer is in your room.
Now, with all that said, your room constraints come into play. There are many in-wall speakers that would suit your needs perfectly, and would be capable of an 80Hz crossover, and would be less expensive than the M20s. Yes, you would have to go through the hassle of running wire and mounting them. The extra bonus is that you will have even more room to get past your seating, since the grilles will be flush to the wall, and no speaker box will jut out into the passageway. The CI Pro P80-IW speakers will sonically match your Prestige setup and can play down to 57Hz (very similar to the 15Bs). In fact, with the Prestige series being discontinued, it may make finding 15Bs difficult.