I was in NYC a week or so ago and did some searching using Google Maps. The problem was that the maps have as much spam as the SERPs - as a result you can't trust the maps because theyl have markers on then for specific locations that are irrelevant. (I wonder how many people drive or walk to these only to figureout that they have been spammed. Sure would be a lot more time-wasting than a couple of spammy clicks).
At first I was very trusting of the map data but then a slow revelation grew in my mind about how the maps are being spammed in a way similar to the SERPs - or else the irrelevent results just creep in through the algo.
Getting back to your original question... In general, I like the idea of paid results shown in blue (just so they don't use them on my mashups). Paid results are more likely to be relevant because the advertiser must have something of interest or he / she would not be paying.
It's not the size of the dog in the fight that matters. It's the size of the fight in the dog.