Realizing quantum speedup for solving practically relevant, computationally hard problems is a central challenge in quantum information science. Using Rydberg atom arrays composed of up to 289 coupled qubits in two spatial dimensions, we experimentally investigate quantum optimization algorithms for solving the Maximum Independent Set problem. We use a hardware-efficient encoding associated with Rydberg blockade, realize closed-loop optimization to test several variational algorithms, and subsequently apply them to systematically explore a class of nonplanar graphs with programmable connectivity. We find that the problem's hardness is controlled by the solution degeneracy and the number of local minima, and experimentally benchmark the quantum algorithm's performance against optimized classical simulated annealing. On the hardest instances, we observe a superlinear quantum speedup in finding exact solutions for sufficiently long evolution times beyond the shallow-circuit-depth regime, and analyze its origins.