<p>Do you refactor your SQL first? Your architecture? or your code base?
Do you change languages? Do you throw everything away and start from scratch? [Not refactoring]</p>

This really depends on the state of the codebase... are there massive classes? one class with mega-methods? Are the classes tightly coupled? is configuration a burden?
Considering this, I suggest reading
Working Effectively with Legacy Code
, picking out your problems, and applying the recommendations.