**UPDATED AGAIN** Here are some lower bounds and the results of $10^6$ random trials. The $1$-dimensional case is quite informative and is discussed at the end.

One way to get an exponential lower bound is to choose an area $1/2$ subset and find the chance that it remains intact after $n$ lines. A tilted square, the intact isosceles right triangle after the first line (if there is one), an optimal octagon and centered circle (in that order) give such bounds which are increasingly good. However an exponential model is not the right one to use.

- The chance that a single line avoids the tilted square with corners $(1/2,0),(1,1/2),(1/2,1),(0,1/2)$ (of area $1/2$) is $1/6:$ With probability $1$, the point first chosen is not a corner of the original square or the tilted one. wlog it is on the left half of the bottom. Then the second point needs to be on the lower half of the right side. The chance of this is 1/6. So the chance that none of $n$ lines cut the tilted square is $$\frac1{6^{n}}.$$

- This can be improved to $$\frac4{6^n}=\frac2{3\cdot 6^{n-1}}$$ by considering instead isosceles right triangles. The chance that the first line crosses two adjacent sides is $2/3.$ If this does happen then one of the diagonals misses this line and splits the square into two isosceles right triangles with area $1/2.$ One is cut and the other intact. For every subsequent choice the first point is outside the intact half with probability $1/2$ and the second with probability $1/3.$

- Here is a certain octagon along with the circle with center $(\frac12,\frac12)$ and radius $\frac1{\sqrt{2\pi}}.$ [![enter image description here][1]][1]
I find that the octagon above is the best of its kind. I get that the probability it stays intact is about $$(\frac{2(0.4797667)}3)^n=0.31984^n.$$ The lower left corner is at about $(0.32606,0.11670).$

- For the octagon, and also the circle, the exact probability of a line missing it can, in principle, be found using several integrals. They are not that nice so I evaluated them numerically. The probability of a line missing the circle is about $.34470989$ hence $$0.34470989^n.$$

  Perhaps some shape of the form $t$circle+$(1-t)$octagon beats the circle. However another octagon might do even better for that process.

------------------------------------------------------------

It is not all that hard to randomly generate lines. One need only keep track of the vertices of the one maximum area region. Then a new line either misses it or intersects two of the sides creating two new vertices and two regions.

In $10^6$ random trials it happened $4$ times that only the $20$th line left all regions with size less than $\frac12.$ Of course the first line is always OK. $187209$ times the second line was fatal, the other $812791$ it wasn't. The counts were

$$[1, 1000000], [2, 812791], [3, 580116], [4, 376623], [5, 228824], [6, 131445],$$$$ [7, 72077], [8, 38186], [9, 19805], [10, 10009], [11, 4852], [12, 2299],$$$$ [13, 1070], [14, 540], [15, 259], [16, 113], [17, 47], [18, 18], [19, 4]$$

As suggested by Emil, the correct model is possibly of the form $f(n) c^n$ for some $f(n)$ with sub-exponential growth. This is supported by the following:

---------------------

Consider the similar problem in $1$-dimension: 

>>The interval $[0,1]$ is divided into $n+1$ subintervals by $n$ random points. What is the probability that the longest subinterval has length at least $\frac12?$

It turns out that the exact answer is $\frac{n+1}{2^n}.$ It is easiest to prove the more general form: Given that the largest currently surviving interval has length $\frac12+x,$ the probability of surviving the next $n$ random points is $$\frac{n(2x-1)+1}{2^n}.$$

Given this exact result, we don't need an upper bound. But getting one helped me understand Christian's method: I claim that an upper bound, valid for all $n$ is $$N\left(\frac12+\frac1N\right)^n.$$ Fix an integer $N>2$ and consider the $N$ intervals $I_t=[\frac{t}{2N},\frac{t}{2N}+\frac{N-1}{2N}]$ with $1 \leq t \leq N.$ A subinterval $[s,s+\frac12]$ contains one of these (move each endpoint inward to the nearest $\frac{a}{2n}.$) If some interval of length $\frac12$ stays undivided, so does at least one of the $I_t.$ The chance that any particular one stays undivided by $n$ random points is $(\frac12+\frac1N)^n.$ So the chance that at least one does is less than $N\left(\frac12+\frac1N\right)^n.$ This is an upper bound on what we seek. 



  [1]: https://i.sstatic.net/vg15U.png