Disclaimer: I identify as Republican (well, Conservative since I'm not American, but same difference). Here's a single person's take (although I believe my opinion to reflect at least mostly the majority Conservative opinion):
Most of what you have said is correct. Reducing the deficit requires additional income. Tax cuts reduce income. Border security and defense take income. These things are contradictory. However, you are missing what is perhaps the most important part of the puzzle, which is the size and scope of government.
In particular, a core tenet of the Conservative ("Republican") worldview is that a) government should be as small as possible, and b) government is very wasteful and inefficient. To create a concrete example (pulling numbers out of my butt here, please don't ask for citations): Let's say you own a company and you have 100 people on staff, each making, let's say $50k/yr. That's $5M/yr in payroll costs for your company. Let's say, for example, that this company has a 75% output ratio, which is to say, on average, each employee is idle for 25% of their time. That means you can, in theory, fire 25% of your employees, offload those employees' work onto the other 75%, and now you will have 100% output (obviously the real world doesn't work exactly like this, but it's close). So you go ahead and fire 25 people. That's a cost savings of $1.25M/yr in payroll, without decreasing company net output (again, simplification warning). Now you can take that $1.25M/yr and put it into, say, R&D, or buying new machinery, or getting a new, swankier office, or whatever else you like.
The government, say Conservatives, is in a similar situation. There are so many government employees whose jobs are redundant, or who simply don't do them properly (e.g. show up late/leave early/slack off, etc), and if we, to use a colloquialism, "whipped them into shape", then we could fire a whole swath of government employees and save money. Then we take that money and use it to pay down the debt, or implement tax cuts, or spend it on border security and defense.
But that's not the only place where the government can save money. Government contracts are well known to be bloated with a ton of money that doesn't need to be spent. For example (unfortunately a dated one but useful for illustrative purposes), here is a post over on Skeptics SE which, in the accepted answer, states that in the 1960s, the US government bought a bunch of mechanical pencils for astronauts at a cost of over $100 each! Now, while it is difficult to know how much money the government is spending on ongoing government contracts (I presume the budget, such as it is, is public information, but where each of those dollars is going and to whom I'm going to guess is probably classified), it is not unlikely that similar such wasteful spending is ongoing in the modern day as well (and even if we did know the breakdown of money spent on contracts, it would be difficult to know how much of that spending is wasteful, and how much is required to do the job). Once again, if the government can spend in a responsible way on their government contracts, then money can be saved which, again, can be put into tax cuts, or defense, or paying down the debt.
Aside: One of the selling points for Donald Trump amongst Conservatives was the fact that, as a businessman, who literally wrote the book on the art of the deal, it was presumed that he would be a good negotiator to try to knock down the costs of some of these government contracts. Unfortunately I don't have numbers to back up whether or not that has turned out to be the case after the fact (a useful edit to this post might include such data if someone else happens to know where to find it).
An additional way in which the government is wasteful is in wasteful social assistance spending. Not to say all social assistance spending is wasteful, that's certainly not true (a true economic conservative may argue that, but most reasonable people agree that some sort of social safety net is important); the part that is true is that currently, there are social assistance programs which are being exploited by people who do not deserve them. As a simple example, I found this article on Google which states that in the year 2013-2014, the state of Pennsylvania (not the whole US, just Pennsylvania) paid welfare benefits to over 2300 dead people. I don't think anyone can rationally argue that dead people should be receiving social assistance. Once again, if we take that money and stop spending it wastefully, then we can spend it on, again, paying down the debt, tax cuts, border security, and defense.
And yes, before anyone says it: The amount of welfare benefits paid to 2300 dead people in one year is peanuts compared to the whole government budget. This is true. However, every dollar helps, and this is but one very simple, very egregious example that I could easily find with a cursory Google search; more examples most assuredly exist, and the government certainly has the tools to find them.
An additional (but somewhat more controversial) way in which the government wastes money is with regards to regulatory structures. There are lots of business regulations in terms of how businesses can operate (one very easy example for illustrative purposes being greenhouse gas emission limits). It costs money for companies to implement these regulations, but it also costs the government money to oversee these regulations being implemented. Someone has to pay for an inspector to go on-site at some manufacturing plant to make sure the employees are being provided, for example, hard hats for construction work (a simple example for illustrative purposes; no reasonable person would argue that providing safety equipment is a negative). Some of these regulations are good and worthwhile, others not as much (and which ones fall into which camp is more or less a matter of opinion, so I'm not going to get into the finer points). Conservatives would argue that the fewer regulations, the better. There are economic reasons to do this from the perspective of the business, but leaving those aside, from the government's perspective, the less regulation there is, the less money you have to pay public servants to verify those regulations are being followed. This decreases the government's cost, and that money can be put into, you guessed it: paying down the debt, tax cuts, border security, and defense.
This is an insight into a Conservative point of view on the issue, I hope it was useful.