Why is lambda calculus so "function" oriented? I've always had this question nagging at me subconsciously but have never been able to intuitively grasp it. Why does $\lambda$-calculus have a functional notation? Why is everything a function?

It seems it has something to do with the evolution of Logic (See History of the Function Concept) and trying to "nail down" what was really meant by a function. Going through the history - FO-logic, intuitionistic logic, combinatory logic, lambda calculus etc., I still am a bit unsure about why did Church go with the function-oriented view of things. I know he was trying to work on a system for foundations of logic/math which led to the creation of $\lambda$-calculus. But what I wish to understand is his thinking and reasoning that led to the use of functions as the vehicle of choice, for getting there.
The idea of how to 'mechanize mathematical proof' was a hot topic at the time; more specifically, Hilbert posed the Entscheidungsproblem - could we have a machine in some factory somewhere that takes mathematical statements in, and outputs proofs of the truth or falseness of those statements, as easily as machines might weave cotton or drill holes in steel?

If one was 'merely' dealing with the mathematical concept of a function, then we can define such a function whose input is a mathematical statement (formally, a first order sentence in the language of number theory) and whose output is either 'True' or 'False'. 

This is perfectly satisfactory as a mathematical function (once one has properly defined what it means for a statement to be true or false) but now one has a constructibility problem; the mere existence is not useful when your main goal is to actually evaluate this function on given inputs.

The purpose of the lambda calculus, and equivalent models such as Turing machines, is to provide this construction. When a mathematical function matches the input/output behavior of a Turing machine, or (equivalently) has a representation in terms of the lambda calculus, then such a function is called 'computable'. 

Gödel's Incompleteness Theorem states that the true/false function described above is not computable. It is generally believed that the only mathematical functions that can be evaluated in the 'real world' are exactly the computable ones (this is the Church-Turing Thesis). Therefore, despite existing as a mathematical function, we have absolutely no way to evaluate that function in general (of course, there are still specific inputs where we can evaluate that function)