Pyth, 29 bytes

This is a direct translation of my CJam answer in Pyth

oc/|$Y.append(N)$YN/zNo_/zZSz

Try it online here

There is a rather long story behind this solution and @isaacg helped me a lot in understanding this new language.

Ideally this is the exact word to word translation of my CJam code (17 bytes):

oc/~kNN/zNo_/zZSz

which means:

o         order_by(lambda N:
 c                 div(
  /                    count(
   ~kN                       k+=N,                #Update k (initially ""), add N
   N                         N),                  #Count N in updated k
  /zN                  count(z, N)),
 o                 order_by(lambda Z:
  _                         neg(
   /zZ                          count(z, Z)),
  Sz                        sorted(z)))

But sadly Python does not return anything in a += call, so that was not a valid Python code, thus an invalid Pyth code too as in Pyth, a lambda can only be a return statement.

Then I looked into various methods and finally found that Python's list.append returns a None value, which I can use. Making the code to be (19 bytes):

oc/|aYNYN/zNo_/zZSz

which means:

o         order_by(lambda N:
 c                 div(
  /                    count(
   |aYN                      (Y.append(N) or
    Y                         Y)                 #Update Y (initially []), append N
   N                         N),                 #Count N in updated Y
  /zN                  count(z, N)),
 o                 order_by(lambda Z:
  _                         neg(
   /zZ                          count(z, Z)),
  Sz                        sorted(z)))

But sadly, support of a (append) was removed from Pyth and the version which do has the support, does not have the support for o.

Update : a support has been added back in Pyth now so the above 19 byte code will work in the online compiler. But since this is a new feature which was added after the OP, I am not putting it up as my score and letting the 29 byte code as my solution.

Therefore I had to rely on raw Python in that case, making the code to be

o         order_by(lambda N:
 c                 div(
  /                    count(
   |$Y.append(N)$            (Y.append(N) or
    Y                         Y)                 #Update Y (initially []), append N
   N                         N),                 #Count N in updated Y
  /zN                  count(z, N)),
 o                 order_by(lambda Z:
  _                         neg(
   /zZ                          count(z, Z)),
  Sz                        sorted(z)))