We'd need a way to verify that these full nodes are really full nodes to be rewarded. We should find some way of having a full node perform some work to prove they're not just a fake node. Maybe they could perform some sort of mathematical computations to prove they're real. And then when they find the right solution to this mathematical problem, we reward them with, say, 25 bitcoins. I think this would work. People would love such a reward and so they will run lots of full nodes!