Just to test my guess, let n = 4.

Then there are 4*3/2 = 6 different possible friendships.

The total possible configurations of friendships and non-friendships are 2^6 = 64.

Of these 23 involve one or more parties having no friends (trust me on this), and will be ignored.

What about the remaining 41 configurations?

Let p = probability of a friendship between any two people be 1/2.  Then all configurations are equally likely.

Of the 41 configurations:

  7 of them have no people whose friends have more friends than they do (again, trust me on this).

 18 have 1/2 of the people with friends who on average have more friends than they.  (For instance, if 5 of the 6 possible friendships exist, which can occur in 6 different ways)

 16 have 3/4 of the people with friends who on average have more friends than they. (For instance, if there are 3 mutual friends, one of whom is also friends to the fourth person, which can happen in 12 different ways)

 

 Altogether, the probability of having friends who on average have more friends than you =

   (18*1/2 + 16*3/4)/41 = 21/41 which is ever so slightly over 1/2.

 So, for n = 4, the proposition is true if p = 1/2.  There is  some slightly larger p for which the proposition is not true.

 

 This is an improvement over the n = 3 case, for which the proposition is true only if p < 1/2.

 

 This reinforces the first of my two earlier guesses:

 (1) As n increases, I expect that the threshold value of p increases, so the statement is more and more likely to be true.

 

 And I still stand by my 2nd guess:

 (2) As n increases, it makes sense that the actual value of p will decrease, so the statement is also more likely to be true.