I understand what you mean by the difference between 16M possible and 16M simultaneous. Having gone thru the Sharp data sheet I can assure you it does 16M simultaneous. Even so that would need 16M pixels on one screen as you already pointed out so we only get about the 1.3M displayed.
Anyway to press on.
Each of the 256 boxes of the 16 x 16 grid contains 64K colours (256 x 256 grid in each box). So on our screen we will have approx 5 x 3.2 x 64K ~ 1M colours present.
If you now set your 8890 display colour depth to 16 bit (ie 5 bits of colour depth per pixel) each of the 5 x 3.2 boxes should show a definite grid of 32 x 32 smaller boxes. This equates to 262K colours (I see this on my Toshiba

which has a 5 bit colour depth LCD).
So now you should be seeing 32 x 32 smaller colour boxes within each of the original 16 x 16 grid, agreed? If you do, we are at 5 bit colour depth (ie. 262K possible colours).
One other thing I also discovered is that setting the colour depth on one screen also alters the external screen (I was not sure of this before). So, if I now move the image across to my CRT (staying in 16 bit mode), I still get 32 x 32 smaller coloured boxes within each of the original 16 x 16 grid.
Now set the 8890 LCD back to 32 bit colour depth.
The obvious colour banding disappears on both my LCD and CRT displays, to be left with a smooth colour gradient. However, and this is important, if you look at the image in one spot for more than about 10 seconds (on either screen type) you will start to see bands of colour that appear to be wider/larger than the small boxes present under 16 bit mode. Do you get that effect? Is that what you are seeing as colour banding or are you seeing still smaller boxes (say 64 x 64 small boxes within each of the original 16 x 16 grid)?
If the colour banding you see in 32 bit mode is producing boxes *bigger* than the obvious small boxes displayed in 16 bit mode then that is an optical illusion (the reasons for which are complex and we will get to those later) not a LCD problem.
But if the boxes are smaller in 32 bit mode than 16 bit mode it could mean one of three things, either our LCDs are actually different models (8 bit vs 6 bit colour depths), or your laptop has a hardware fault or our software is different.
Let me know your results from the above tests. I am about to get some shut eye so we will pick this up later.