Here is a nice ad hoc start: The set $S=\lbrace 0, 1, 3, 5, 6, 13, 15, 16, 18, 25, 26, 28, 30, 31 \rbrace$ has $S+S=\lbrace 0,1,2,\cdots,62 \rbrace$ (It is the start of [a sequence in the OEIS][1] with next term 63,  but I'm not sure if that helps). Then $T=S+63S$ has 196 members the largest being $1984$ and $T+T=\lbrace 0,1,2,\cdots,3968 \rbrace$. Now $14=31^{0.63944}$ and $196=3968^{0.63699}$ and further iterating will continue to give examples sparser than $k^{2/3}$. The same trick can be done with any finite example. The densities decrease but only very very slightly.
**LATER** the set $S'=\lbrace 0, 1, 3, 5, 6, 13, 14,17, 18, 25, 26, 28, 30, 31 \rbrace$ also has $S'+S'=\lbrace 0,1,2,\cdots,62 \rbrace.$

Observe that the places where $S$ has a jump from $j$ to $2j+1$ are at $0,1,6,31$ (numbers of the form $\frac{5^j-1}{4}$) and that there is a central symmetry for $0,1$ and for  $0,1,3,5,6$ and for $S$. This suggests a treasure hunt for an symmetric extension with largest member $1+5+25+125=156$.

**UPDATE** For any one of the four choices $(a,b)=(68,69),(68,72),(69,70),(70,71)$ the set  $V=S \cup \lbrace 63, 64, a,b,156-b,156-a, 92, 93  \rbrace \cup (S+125)$ has $36$ members, the largest being $156$. and $V+V=\lbrace 0,1,2,\cdots,312\rbrace$ There is only one way to similarly extend $S'$ to a set of size $36$ with the same properties, it has lower half $S' \cup \lbrace 63, 65, 67, 69 \rbrace$. These are better than the examples above since $36=312^{0.62398}$. Also, these can be iterated as above.

 Maybe an even lower density is possible for $W=V \cup \lbrace ?? \rbrace \cup(V+625)$ where the set in the middle is made of several pairs $q,781-q$. I'd guess 8 pairs leading to $88=1562^{0.60885}$ but that is pure speculation.  Of course there might be better examples which are not symmetric (or even ones which are). There turns out to be no advantage at this stage to putting the exact middle of $78$ in $V$ (for any of the 5 choices). I don't think it would help get a better $W$ but I am not sure.


  [1]: http://oeis.org/A108337