The exponent can be arbitrarily close to $\frac{1}{2}$: If $n=r^2$ then $A+B=\lbrace 0,1,2,\cdots n-1 \rbrace$ where $A=\lbrace 0,1,2,\cdots r-1\rbrace$ and $B=\lbrace 0,r,2r,\cdots,(r-1)r\rbrace$. This means that $S=A \cup B$ is a set of size $2r=2\sqrt{n} $ with $S+S \supset \lbrace 0,1,2,\cdots n-1 \rbrace$. So by iteration (as described in the old answer) we can have exponent $\frac{1}{2}+\log_n(2)$.
Modifying this a bit gives a construction I probably have seen before: Let $A=\lbrace 0,1,4,5,16,17,20,21\cdots\rbrace$ be the (infinite) set of non-negative integers whose binary expansion is $0$ in all the odd positions and $B=2A$ the set of those with $0$ in all the even positions. Here both have exponent $\frac{1}{2}$ and $A+B=\mathbb{N}_0$. Then $S=A \cup B$ has about $2\sqrt{N}$ members less than $N$ and $S+S=\mathbb{N}_0.$
Old Answer 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 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.
Best Answer
Given an integer $n$, the Jacobsthal function $g(n)$ is the least integer, so that among any $g(n)$ consecutive integers $a,a+1,\dots,a+g(n)-1$ there is at least one that is coprime to $n$. Let $\nu(n)$ count the distinct prime factors of $n$. You can define $$C(r)=\max_{\nu(n)=r} g(n)$$ and as Jonas Meyer points out in the comments this is precisely $C(t)=\gamma (t)$ (i.e. it is enough to consider when all $a_i$ are prime).
For the bounds $$\frac{c_1t (\log t)^2 \log \log \log t}{(\log\log t)^2}\le C(t)\le c_2 t^{c_3}$$ see the paper "On the integers relatively prime to n and on a number-theoretic function considered by Jacobsthal"" by Erdos. I don't know if there are better bounds.