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).