After mulling it over, I think we need a third party presidency for budget deficit reduction to become a sustained, acted upon priority.
Pew has tracked public prioritization of reducing the nation's federal budget deficit for nearly twenty years, and from someone whose default position is one of starving the beast, looking at how partisan positions flip flop depending on which party controls the presidency makes for depressing viewing. The following graph shows the percentage of survey respondents indicating that budget deficit reduction (from '02 onward; prior to that the query was on paying off the national debt, which, while not the same thing, captures similar sentiments) should be a top governmental priority. Results come from surveys conducted in January of each year:
During Clinton's presidency, Republicans cared more about cutting the deficit than Democrats did. Under Bush that flipped, and during Obama it flipped back again. It makes sense if you're all for redistributive spending so long as your guy is the one doing it. It doesn't make so much sense if your party is putatively the one opposed to leviathan's accretion, however.
It's often said that reducing the deficit and restoring fiscal sanity is important in determining the world that older generations will leave to their kids and grandkids, but those kids care less about it than their elders do. Of the 21 issues examined, the only one with a wider old-young (50+ and 18-49 years, respectively) gap is "securing social security", for obvious self-interested reasons.
There might be some reason for cautious optimism, though. Over the last decade, the trend has been upward across the political spectrum, and the GOP now has a high profile champion or two on the issue.
Pivoting to provide Republican pols with political advice, how about emphasizing opposition to gun control? While it's politically savvy, it's not pusillanimously appeasing--a state's gun ownership rate is one of the strongest predictors of how it votes. The higher the rate, the redder the state. And of the 21 issues Pew asked about prioritizing, gun control garnered the highest "should not be done [at all]" response rate of all.
Opposition to restrictions on firearm capacities and ownership is highest among the young, the wealthy, and the well educated, while support for increasing restrictions is highest among the old, the poor, and the uneducated. Excepting the political angle, contemporary demographic trends on the questions of gun control and same-sex marriage are pretty similar. Unlike a lot of other 'social issues' that see the conservative standing athwart history yelling "stop" (which, while I'm personally sympathetic to, is usually portrayed and conceived of in the popular consciousness the antithesis of being hip and forward-thinking), the right to bear arms is important to people who are going and who have gone places in their lives.