Perl 5 -n, 201 bytes

%s=map{/ /;$r{$`}=1;$v-=3;$`=>$'}<>;delete$s{DC};map{%A=map{$_=>$s{$_}/sqrt($r{$_}*($r{$_}+1))}@k=keys%r;++$r{(sort{$A{$b}<=>$A{$a}}@k)[0]}}1..$v+$_;say"$_ ",2+$r{$_}for sort{$r{$b}-$r{$a}||$a cmp$b}@k

Try it online!

Swift 6, 248 bytes

let e={var s=($0 as[_:_]).map{($0+"",$1+0,1)},c={.init($0+0)/Float(($1+1)*$1).squareRoot()}
for _ in 0..<$1-3*s.count{s.sort{c($0.1,$0.2)>c($1.1,$1.2)}
s[s.index{$0.0 != "DC"}!].2+=1}
return s.sorted{$0.2==$1.2 ?$0.0<$1.0:$0.2>$1.2}.map{($0,$2+2)}}

Try it on SwiftFiddle!

Python 2, 219 bytes

v,s=input()
n={k:1 for k in s}
v-=3*len(s)
l=lambda x:-x[1]
if'DC'in s:del s['DC']
while v:A,_=sorted([(a,s[a]/(n[a]**2+n[a])**.5)for a in s],key=l)[0];n[A]+=1;v-=1
for a in n:n[a]+=2
print sorted(list(n.items()),key=l)

Takes input as

420,{'K':123,'L':456,'M':789}

Prints:

[('M', 241), ('L', 140), ('K', 39)]

Clean, 263 244 222 bytes

v n s=sortBy(\(a,b)(c,d).b>d)([(t,3.0)\\t<-s|fst t=="DC"]++w(n-3*(length s))[(t,1.0)\\t<-s|fst t<>"DC"])
w 0s=w 0 s=[(p,r+2.0)\\(p,r)<-s]
w n s#s=sortBy(\a b.A a>A b)s
#(p,r)=hd s
=w(n-1)[(p,r+1.0):tl s]
A((_,p),r)=p/sqrt(r*r+r)

Call like

Start = v 538 [("DC", 1000000.0), ("RH", 1.0)]

Ungolfed version, full program (census.icl):

module census

import StdEnv

Start = votes 538 [("DC", 1000000.0), ("RH", 1.0)]

votes n states
# dc = filter (((==)"DC")o fst) states
= sortBy (\(a,b)(c,d).b>d) ([(t,3.0) \\ t <- dc] ++ votes` (n-3*length states) [(t,1.0)\\t<-removeMembers states dc])
where
    votes` 0 states = map (\(p,r).(p,r+2.0)) states
    votes` n states
    # states = sortBy (\a b.A a > A b) states
    # (p,r) = hd states
    = votes` (n-1) [(p,r+1.0):tl states]

    A ((_,p),r) = p / sqrt(r*r+r)

JavaScript ES6, 249 bytes 244 bytes

(r,s)=>{r-=s.length*3;s=s.map(t=>({s:t[0],p:t[1],a:t[1]/(q=Math.sqrt)(2),r:1}));while(r--)(t=>t.a=t.p/q(++t.r)/q(t.r+1))(s.filter(t=>t.s!='DC').sort((a,b)=>b.a-a.a)[0]);return''+s.sort((a,b)=>(r=b.r-a.r)?r:a.s>b.s?1:-1).map(t=>t.s+':'+(t.r+2))}

Test cases

d = (r, s) => {
  r -= s.length * 3;
  s = s.map(t => ({
    s: t[0],
    p: t[1],
    a: t[1] / (q = Math.sqrt)(2),
    r: 1
  }));
  while (r--)(t => t.a = t.p / q(++t.r) / q(t.r + 1))(s.filter(t => t.s != 'DC').sort((a, b) => b.a - a.a)[0]);
  return '' + s.sort((a, b) => (r = b.r - a.r) ? r : a.s > b.s ? 1 : -1).map(t => t.s + ':' + (t.r + 2))
};

document.write(
  '<pre>' +
  d(135, [
    ['C', 236841],
    ['D', 55540],
    ['G', 70835],
    ['K', 68705],
    ['M', 278514],
    ['Ms', 475327],
    ['Nh', 141822],
    ['Nj', 179570],
    ['Ny', 331589],
    ['Nc', 353523],
    ['P', 432879],
    ['R', 68446],
    ['Sc', 206236],
    ['Ve', 85533],
    ['Vi', 630560]
  ]) +
  '</pre>'
);

Credit to @Neil for saving 5 bytes!