"Rationalist" and "empiricist" are technical terms in philosophy, and they don't mean what you might think they mean based on common usage of the words "rational" and "empirical". The SEP puts it like this:
Rationalists claim that there are significant ways in which our concepts and knowledge are gained independently of sense experience. Empiricists claim that sense experience is the ultimate source of all our concepts and knowledge.
Two important things to note about this definition: it doesn't imply that rationalists in any way disregard empirical research, and it doesn't imply that empiricists are in any way not rational. The difference is strictly a question about how we know things about the natural world that we apparently didn't get from our senses.
For example, I ask you how many people will be at dinner and you say eleven, so I set eleven places at the table. I know that there will be one place setting for each diner and one diner for each place setting even before most of the diners have yet to show up. How do I know this? I've never before seen a dinner table with eleven places or eleven diners, and even if I had, I wouldn't be able to identify it because I can't recognize numbers higher than three or four without counting.
You might answer, "Well, the answer is that you counted", but that was a purely mental process; it wasn't a sense impression; it was something that I did in my mind. So how do I know that something I did in my mind rather than experienced in my senses is going to tell me something true about the natural world? A rationalist would say that mathematics is rational knowledge that comes to the mind from some source other than observation. An empiricist would reject this answer.
Before the late nineteenth century, an empiricist would answer that mathematical knowledge is in fact empirical knowledge that we get from sense impressions. They had some rather far-fetched explanations for how this could be. Then along came a philosopher/mathematician named Gottlob Frege who offered another explanation: mathematical knowledge isn't actually knowledge; it's pure logic.
As I said earlier, empiricists are not irrational. They don't (in general) reject logical laws like the law of the excluded middle or modes ponens. So if they can prove that mathematics is nothing more than a sophisticated application of logic, then that solves their problem with mathematics, and there is no need for some other source of information about the rational world.
However, as the question points out, we need some form of innate knowledge just to make sense of sense data. Consider for example, language. How does a baby know that consonants are relevant to meaning, but the differences between his father's voice and his mother's voice are not relevant to meaning? Empirical research indicates that human beings have built-in mechanisms to understand language. You couldn't make up just any random language with any random set of vocalization because the human mechanism for recognizing language expects certain rules to be followed.
Even more fundamentally, empirical decision making depends on recognizing when two objects or two situations are similar and when they are not. How do we recognize this? There is something built in to our sensory apparatus and our brain that makes these judgements for us. Even more fundamental than that, how do we recognize objects? How do we recognize that the apple hanging from the tree branch is a distinct object which can be considered separately from the entire tree? Again, it's something built in to our brains.
However, it might be worth making a note about philosophical tradition. One does not describe this problem by saying that empiricists must be rationalists because that is rather insulting, and philosophical arguments should be rational and temperate. Instead, one says that these issues are problems for empiricism, or reasons that empiricism cannot be true. This is more polite; it doesn't say, "You don't even know what you believe!" it says, "Here's a problem for you, how would you answer it?"