A heuristic for finding a maximum disjoint set
Rather than your approach, I suggest you formulate this as an integer linear program and feeding it to an off-the-shelf ILP solver.  Alternatively, formulate it as a SAT problem and feed it to a SAT solver: you'll probably need to take the decision problem version, where you ask whether there exists a subset of $k$ non-overlapping squares, and then use binary search on $k$.  Those would be the first approaches I would try, personally.



If you definitely want to try your approach based upon a "separating line", then I think the best way to answer your question is going to be to pick a representative set of problem instances, and try some different heuristics on them to see which seems to work best.

My intuition suggests that the best way to select the separator line may be to pick the line $L$ that intersects as few squares as possible, without worrying about how balanced the division is (though if there is a tie among multiple lines that each intersect the same number of squares, you could always use "how balanced the division is" as a tie-breaker).  The reason is that you are getting an exponential multiplicative increase in the running time each time you enumerate all subsets of the squares that intersect the line $L$.  I think your prime consideration is going to be keeping that blowup down.  But that's just my intuition, and my intuition might be wrong.  I think you need to do the experiment to find out empirically what works best.

If you do apply your separating line approach, you might consider using a branch-and-bound approach.  Keep track of the best solution you've found so far (i.e., the largest set of non-overlapping squares you've been able to find so far); say that it is of size $s$ at any point in time.  Now anytime your search tree enters a subtree where you can prove that all solutions below the subtree will have size $\le s$, there is no need to explore that subtree.  For instance, if you have a line $L$ and a subset $X$ where you know that the size of $X$ plus the size of the largest sub collection of non-intersecting squares above $L$ plus the total number of squares below $L$ is $\le s$, then there is no need to recursively compute the largest sub collection of non-intersecting squares below $L$, which saves you one recursive call.  But, if you use an off-the-shelf ILP solver, it will already implement these sort of branch-and-bound heuristics for you -- hence my advice to start by formulating this as an ILP problem and applying an off-the-shelf ILP solver.



Finally, the following paper apparently describes an $O(2^{\sqrt{n}})$ time algorithm to compute the exact solution to your problem.  This is an improvement over the obvious algorithm that enumerates all possible subsets of squares, which takes $O(2^n)$ time.

An application of the planar separator theorem to counting problems.  S.S. Ravi and H.B. Hunt III. Information Processing Letters, Volume 25, Issue 5, 10 July 1987, Pages 317–321.
http://www.sciencedirect.com/science/article/pii/0020019087902067