Stating the title in another way, how to convince a strong applied CS department that a theorist would be a better choice than one more applied computer scientist?
I understand that it is natural for a applied department to want one more expert on a specific field. On the other hand, diversity is important and I think the importance of a theorist goes beyond better theory courses.
What is the importance of a TCS researcher in a mostly applied CS department?
I am really not qualified to give an informed answer to your question, but there are many reasons for which a theory-oriented researcher might be a good fit for a more applied environment.
The main reason that comes to mind is this: good theoretic foundations are invaluable for a thorough understanding of an application which in turn increases trust, efficiency and decreases mental effort. In general it allows work to proceed much faster, as the foundations provide a mental reference that can be easily extended or made explicit.
I'm sure there are many examples in complexity theory, where an abstract approach has led to fantastic practical improvements in concrete implementations, but the field I am the most familiar with is "theory B", in which programing language design has greatly benefited from advances in pure computing theory research.
Haskell is a particularly good example. On the theory side, we have simple core languages like system $\mathrm{F}_\omega$ which have proven to be a very useful base for the core language of the GHC compiler. The research in type inference/reconstruction and more recently, on dependent types has guided the foundations of the Haskell design, including the Hindley-Milner architecture and GADTs. Monads, of course, were introduced in the from the most abstract domain of mathematics to the computing world by Moggi, a theorist.
More pragmatically, knowledge of the theory of operational semantics turns out to be an invaluable tool for language extensions: the paper which introduces Software Transactional Memory in Haskell has explicit operational semantics for the small sub-language containing the STM constructs. This creates a reference for the implementation, and the ability to prove properties about a correct implementation, creating trust and understanding.
All this point to the fact that having a strong theory background is an important asset of every research team, including those with a strong application theme.
In addition to the points given in the other answers, I think any CS department offering an Undergraduate programme must have a reasonable number of faculty from the various CS communities, irrespective of what its broad leanings. Otherwise, a new student joining the department would naturally get aligned with the departments focus, without much of a choice. An applied professor may be able to teach TCS courses (and vice-verse), but would be unlikely to be able to pique the student's interest in the same.
heres another angle on this. the question starts out with an a priori "hard sell" situation/case ie a dept that is mostly applied is already going to have an inherent bias against a more theoretical researcher, otherwise that researcher would already be in the dept.
one possible direction "in" is the following. an often overlooked area of software development/design in industry and sometimes computer science departments is architecture. sometimes even TCS does not have large awareness of architecture either, but it is better positioned to recognize it than with applied focus.
in a few words, software architecture is the study of complexity in the solution/software, and ways of minimizing it, which is a major issue esp. with large software projects, which these days are increasingly more common.
software architecture involves in part the choice of algorithms (ie choice among equivalent algorithms, in terms of input/output relationship, based on different performance and scalability characteristics). sometimes applied workers are not even familiar with the basic theory that tells you stuff like an indexed column on a database is $O(log(n))$ access time instead of $O(n)$ and why this is in fact a "big deal". architecture is also tied with very practical topics like when refactoring of code is appropriate or not.
also it seems like some complex commercial software has many dimensions of scalability. in robotics an analogous concept is "degrees of freedom". the software scales in many separate dimensions. for example, memory size, size of web pages, size of database results, etcetera. a good theoretical researcher will be able to more systematically/scientifically assist in identifying and quantifying all these dimensions, ie using the scientific method. more applied workers will tend to just resort to trial and error, sometimes over a period of years, never really understanding exactly why their software is underperforming, hitting internal ceilings, or failing.
there are a few rare researchers who can cross between theory and applied realms without difficulty, or as the vernacular goes, "feet in both worlds". maybe studying them in particular (their career directions and writing, etc) will help to develop the mindset and philosophy to "cross over". in particular, Grady Booch is one eminent figure who comes to mind. he invented much of the concepts behind OOP programming and has much excellent research/writing on the topic of software architecture. another similar researcher is Phillip Kruchten. and yes [as in comments], Peter Shor.
having worked with both, one possible distinction is that in a more applied setting the main deliverable is code and in a more theoretical setting the "deliverables" are analyses/paper(s). this can cause a cultural gap if not everyone is "on the same page" with what are the deliverables. in this case the theoretical scientist will be the one who will have to bend & be more flexible and also "be ok" with that. so the personality of this key person will be a key factor.
another emerging/very prominent area these days that has strong interdisciplinary connection/overlap between theoretical and applied scientists is datamining, reaching larger prominence with official government/corporate initiatives into big data (and again architecture is a foremost element in this).
