The issue you only now realize is the lack of well connected peers throughout the network.
The solution is more full nodes.
Surely you also now understand raising the block size is not ideal nor desired as it stands.
as it stands, no i am forced to conclude raising block limit any higher then a few MB's will start to cost to much in terms of bandwidth for home users to stay online.
with optimizations, i believe 500MB block limit will be the absolute limit for most home users.
i think gavin banking on tech improving enough to allow for GB blocks in a matter of years is very optimistic. maybe he doesn't care too much that full nodes no longer run on home networks....

Optimizations like everyone running SPV I suppose....
Again, you can "optimize" overhead and inefficiencies, but you still have to communicate the whole block of data. There's no way you get around that.
1) making sure the gossip network actually does make every peer on average use 503Bytes to get everyone to hear about a 500Byte msg.
2) communicate new blocks by listing all the TX ID's in that block instead of in full.
wtv it takes.