What should someone who has been rejected from all PhD programs do to improve their application for later admissions cycles?
It's difficult to really answer your question without actually seeing your application, but here's some general advice.


Remember that the admissions process is random. — There is nothing you can do to absolutely guarantee admission anywhere.  The most you can do is maximize your expected return.
Calibrate your expectations. — Are you really a good candidate for a top-5 department?  (Hint: Do you have a STOC/FOCS/SODA paper?)  For a top-10 department?  For a top-25 department?  Really?  Be respectful but brutally honest with yourself.  Ask your letter-writers or other faculty mentors to be brutally honest with you as well.  Listen to them.
Identify potential advisors. — Every department you apply to should have at least two faculty, preferably more, whose specific research interests closely match yours.  Your research statement should not only name those faculty but explain why you think they'd be a good match.  Ask your references (or other mentors) for feedback and advice.  Listen to them.
Spread your applications. — The rule of thumb I heard when I was applying was apply for four schools where you have a reasonable chance of being admitted, one or two backup schools, and one dream school.  Do not let the backup schools know that they are backup schools!
Get good letters. — Your letters must address your potential for research in personal, specific, and credible terms.  A letter that only describes your performance in class is worthless.  Your letters must come from research faculty — not PhD students, not postdocs, not lecturers, not managers.  If possible, your references should have direct experience with strong PhD students (either as a reference or as an advisor) to make direct comparisons.  If possible, your references should be well-known active researchers, but this is actually less important than experience with students.  Since you've taken half a dozen graduate classes, you should be in good shape here.
Write a good statement. — Your research statement (or "statement of purpose" as everyone bizarrely insists on calling it) must address your potential for research in specific and credible terms.  Do not start with an inspiring quotation.  Do not write about how computers are changing the world.  Do not write about how you've been programming since you were in the womb; nobody cares.  Write about your research.  Describe your experience.  Describe your specific interests (not just "theoretical computer science").  Describe a problem that you might want to work on, with enough background and technical language to convince the reader you know what you're talking about and that you actually care.  Bonus points if you correctly cite one of your potential advisor's recent papers, but don't force it.
Get feedback. — Send the final version of your research statement to your letter-writers (or other faculty mentors) and ask for their brutally honest feedback.  Give them plenty of time.  Expect to get your statement back soaked in red ink.  Expect different people to give you conflicting advice.  Listen to all of them.  Lather, revise, repeat.
But this is all about the form of the application.  The best way to improve the content of your application is DO RESEARCH.  Get paid to do research if you can, but do research anyway if you can't.  Find a mentor (at your undergrad institution?) if you can, but do research anyway if you can't.  Post technical questions and answers to cstheory.stackexchange.  Follow CS theory blogs and read the papers that they write about.  Keep a copy of the most recent STOC or SODA proceedings nearby to read while you're compiling, or waiting for the laundry, or riding the bus, or whatever.  Talk regularly with your letter-writers about your progress.  Write, write, write.