Here's an idea: Reject blocks larger than 1 megabyte that do not include a total reward (subsidy+fees) of at least 50 BTC per megabyte.
"But miners can just include a never broadcast, fee-only transactions to jack up the fees in the block!"
Yes... but if their block gets orphaned then they'll lose those "fake fees" to another miner. I would guess that the incentive to try to push low-bandwidth/CPU miners out of the network would be overwhelmed by the disincentive of losing lots of BTC if you got orphaned.
That might work, but it is probably worth while not to un-cap the size limit, just raise it to something that wouldn't cause problems if someone *did* choose to blow a few hundred or thousand bitcoins on blowing up the network. Someone who hacked half a million coins some years back could easily be out there who'd love to blow up the whole shebang for just a few tens of thousands of coins...
-MarkM-
EDIT: As to eight decimals, it provides price granularity, so your transactions of at least one whole bitcoin have plenty of granularty for representing many different fractions of prime or almost-prime larger numbers. It need not mean transactions of less than a whole coin are to be encouraged.