tl;dr: When you teach with the OO paradigm, you get to control the flow of ideas and the level of complexity at any moment.
Here we examine the first course in computing, no matter the educational level. Presumably this is for a formal course, though it can be adapted to self-study. Presumably the students have mixed ability and backgrounds, neither all superstars nor laggers.
In my view, the purpose of the first course is to teach students how to program. It is not to teach them a particular language, and not to teach them the esoterica of that language. How you proceed in practice depends on your own background (the teacher or learner) and on the language you choose. Actually the dependency is not on the language itself, but on the paradigm that the chosen language embodies.
In order to learn how to program, you must first have a concept of the nature of a program within a paradigm. But we are burdened by our history: the history of programming languages and the history of how the instructor learned how to program. So we first consider the question What Is A Program. The answer depends on the paradigm. Leaving out assembly language, in which the program is a sequence of simple statements and branches, we have several possibilities.
Fundamental Nature of Procedural Programming
Languages like C and Pascal were designed in an era in which it was discovered that go-to (branch) programming led naturally to unreadable and unmaintainable programs. Dijkstra, Hoare, and others came to the realization that Structured Programming was superior and sufficient. In Structured Programming the fundamental program structures are sequences of statements, selection of alternatives, and repetition. These can be represented explicitly in languages without reference to branching. They can be explained as branching, but it is not essential to think of them in that way. Combining this concept with the idea of (procedural) abstraction (naming coherent parts of a program and invoking them by name) produces the following way to think about the nature of a program:
Envision a problem, for which you do not yet have a solution, as a set of sub-problems. If they all had solutions a known synthesis would let you combine them into a solution of the whole. Note the two requirements: (1) the set of sub problems must be complete and cover the whole, and (2) a synthesis of solutions is known that would combine them into a solution of the whole. The sub problems themselves may have no known solution, but they must be solvable.
For each sub problem does not have a known solution, recursively decompose it just as above. A solution should be a simple program (procedure) that satisfies all of the requirements of that (sub) problem. If you cannot provide the solution, then recurse until you can solve all of the smaller problems.
Once you have solutions to all the small problems build up a solution to the whole from the lower level syntheses, which were known, and which drove the decomposition in the first place.
Thus the nature of a program is a tree of solutions, with each leaf a (hopefully) simple procedure/function. Each procedure/function solves some part of the original problem. The larger problem is now envisioned as a tree of problems and associated sub problems.
If you teach in C or a similar procedural language in the first course then the most important task is to give students practice with this process. Never mind all of the intricacies of int values and mutation, and pointers, etc. They must learn to understand the nature of a program. Everything else is in fulfillment of this goal. If they learn that, but not the whole language, they can fill in those details later, or on their own. Without that structure they will write terrible programs with long and unwieldy structure, and impossible-to-decipher functions.
Fundamental Nature of Functional Programming
The first Functional Language was Lisp (List Processing). It was developed based on Church's ideas on the Lambda Calculus. Functional languages are provably as powerful as those based on Turing Machines - a famous result. Lisp was originally thought to be inefficient since it incorporated an inefficient garbage collector, and that unfortunate judgment has stuck, though modern functional programs can be as efficient (or even more so) as those of other paradigms. Lisp has many modern successors, especially Scheme and Clojure. While Lisp traditionally uses only an abstract syntax (parenthesized lists), other successors have a concrete syntax that appeals to many (including this author). Languages like Standard ML and Haskell fit in that category.
A functional program is best thought of as an expression, which, if evaluated, produces a value. Since functional languages tend to be incredibly regular, the "value" returned by evaluating an expression might, itself, be another expression. I will used Scheme to explain ideas as we continue. In functional languages with syntax, things will look different, but reduce to the same ideas.
In Scheme, a program and its data are represented by lists: (a b c d). If the list is evaluated it is a program in which the first element is a function (expression) and the rest are the arguments (also expressions) to that function. However, the list need not be evaluated, in which case you can think of it as data (or as an expression to be evaluated later).
Different functional languages differ in when the arguments to a function are evaluated. Originally they were evaluated eagerly, before the function itself is invoked. However, it is also possible to design a language so that evaluation of expressions is delayed until they are actually used. Each has advantages and disadvantages, so functional languages usually compromise (using special forms and macros) so that some expressions use their own distinct rules.
Another feature of an expression only language is that you do not have side effects, only values. Output to a printer and graphics construction are not functional concepts, so special forms can again come to the rescue to provide the possibility of side effects, though most programs work to minimize and localize them.
A pure functional language (or the pure core of a more complete language) will be without special forms and side-effects. In a pure functional program the programmer constructs an expression which will produce the required solution to the problem if evaluated. Smaller scale problems are represented as the arguments to that initial expression and they can also be (recursively) arbitrarily complex expressions themselves. Evaluation of the original (top level) expression implies that the arguments are also evaluated in some order dependent on the language.
Since people do not like to write arbitrarily complex expressions, it is also possible to name expressions (abstraction) and invoke them by name. These names are usually called variables but normally they do not (cannot) actually vary. Once a name is bound to an expression (creating a variable) that variable cannot be bound to another, though the name can be reused - a confusing distinction, of course, until you understand scope. Data in most functional programming languages is immutable. One constructs new lists from old, rather than modifying a given list.
So, beginning functional programmers need to understand the expression, subexpression concept and practice it. They also need to learn at least a few special forms and how they behave differently though they actually look the same. For example, an if-then-else selection structure is normally a special form since eager evaluation of the "then" and "else" expressions is usually not desirable (especially if either has side-effects). As their experience with the language grows they need to learn more about the special forms and their individual rules.
There is an additional task for the beginning functional programmer. Normally repetitions (while, for) are not used in functional languages. They are replaced by recursion, especially tail-recursion. So the beginning programmers need to learn how to pose complex problems recursively with a special focus on tail-recursion. This results in some beautiful idioms that can be mind-blowing when first encountered. For example, reversing a list in Scheme can be done in linear time if you know how, but a naive program will likely be quadratic. The programmers do not need to learn more of the language to do this - there is very little "language" to learn - but must learn more of how to use the language, often by thinking recursively in powerful ways.
Fundamental Nature of Object-Oriented Programming
The first object-oriented language (OO) was Simula, which was developed to facilitate the creation of complex simulations, say of industrial equipment or governmental systems. This may be a key to how to teach the paradigm to novices. See this answer to a different question, for example. C++ was conceptually based on Simula. The next OO language was Smalltalk and most object-oriented languages derive from it. The most direct successor to Smalltalk is Squeak, which is a beautiful choice for teaching, but seldom used outside a small circle.
Imagine a problem that you can conceive of as being solvable by some set of things, each of which has the ability to act on request and to return some information based on those actions. Think of how you would design those things. Each of the things itself has a problem, its piece of the original, and that smaller problem is solvable by additional things with the same sort of capabilities. The things are heterogeneous (many kinds), some simple and some complex. Simple objects can be coded in a language, but complex ones need to be further decomposed.
An object-oriented program is envisioned as a web of objects (things), perhaps just one, that cooperate in the solution of a problem. An object itself is a bundle of behavior that provides services normally for other objects. The web arises from the fact that any object can hold a reference to other objects with which it can communicate - eliciting behavior. Each object takes responsibility for some part of the solution. An object is a value that can be queried for information to solve its own piece. Additionally, it can be directed to act in creation of the final result. Communication with an object is called a message. Both the queries and the actions often (usually) cause additional messages to be sent to other objects, which aid it in fulfillment of the query or action.
Additionally, and this is the important point, objects are themselves constructed, mainly out of other objects (recursively): their parts. They communicate with their parts in the same way (messages) that they would communicate with an "external" object. Thus, the structure of an OO program is a web/graph of communicating objects that are themselves (recursively) webs of objects at a lower level. The execution of such a program is a flow of messages that cause actions and return results from queries.
To create such a program, from scratch, you define one or more objects (using classes in Java or prototypes in JavaScript, etc.) and send a message to an object to start the computation.
OO languages have many features, usually including inheritance, which is often thought to be the biggest idea in the paradigm. In fact, it is not. The big idea is that OO enables the programmer to consistently build complex objects out of simpler parts by composition, keeping the parts essentially invisible to the clients of the object (encapsulation). Variables, other than references at the top level, are used to refer to the parts of an object so that it can maintain a consistent internal state and provide the public services.
In effect, an object provides an abstraction layer, above that of the language itself, in which the programmers building the system can think and extend, without reference to lower-level constructs, even those of the base language itself. Thus a set of objects provides a world that is self-consistent and complete enough to solve the question at hand. Once such a world exists, even novices can program within its framework and can think at that new virtual level. Thus, once a world with, say wombats, food, predators, etc has been provided, perhaps by the instructor, students can extend it, and can solve complex problems within it by creating objects and their web of interactions.
A beautiful OO program is one in which the objects themselves are simple, with simple methods. The complexity is not in the objects themselves, but in the interactions. When I am writing an OO program, I start to get "itchy" when any method has more than about three statements. Any structure nesting (if, while, ..) beyond two is cause for concern. McCabe's cyclomatic complexity metric should give you really small numbers. An implication, of course, is that there are lots of objects, and often, lots of classes. Fortunately, modern IDEs make these easy to create and manage.
Teaching the first course
You can teach the first course in just about any language and within its associated paradigm. If, however, you confuse your students about the nature of a program in that language you have failed.
The students should also write beautiful programs that their mothers would be proud of. The techniques you teach them should scale to larger programs than what they write in the first course. It should never be necessary for any student to unlearn bad habits and bad practices. If they can only program by writing two-page functions/methods filled with deeply nested selection and looping structures they are failing. The parts they build in whatever language/paradigm need to be small and understandable.
Consequences for teaching the first course (focus on OO)
If you need to teach a course and intend to do so without any preparation, the procedural paradigm is likely the easiest for you. You need a suitable language, a compiler, and an editor. The language provides the "stuff" of programming in its few data types and program structures. To be a success here, giving students the essential idea of procedural programming, you will need to find interesting problems. This is difficult since your tools are so primitive. You will also need to guide them into the problem decomposition and program composition to build up the two trees (problem - solution). They often tend to do too much in a given function. Make them factor out every difficult bit and apply intention revealing names to the parts factored. Require then to use short functions, limited nesting of program structures, etc.
If you want to teach OO programming, on the other hand you need to prepare before the students begin. You need to have in hand one or more virtual worlds found, or constructed by yourself, in which they can do interesting things. Making it interesting is easier, since the structure of the world is up to you. Students programming in one of your worlds can start out with nothing more than sequences of messages to one or more objects to get some desired effect. If your world is graphical, all the better, since the students can see the effect of their program, and hopefully where they go wrong when they do.
Next, in the OO world, students can extend one of your (say class) structures to add some additional behavior. They can do this by inheritance if the language permits or not. I would strongly suggest that you not overemphasize inheritance. Certainly avoid deep inheritance hierarchies. Ignore the concept of "reuse" and instead just extend the made-to-order world with interesting behaviors and/or objects. Since you have built the virtual world, you can control the order in which ideas are presented to the students and can control the complexity of what they must deal with at any moment. You can introduce deep concepts in a simple way in order to achieve some local small/scale effect as well. Not every program needs to be math-like as you have richer things than integers, etc.
If you want to teach them OO programming, do not think that you first have to teach them procedural programming. Some of the ideas of procedural programming naturally occur in writing methods of OO programs, only in a smaller scale. It is easier to move from OO to procedural than the other way, actually, since the methods written are a lot like the procedures/functions of the procedural paradigm. It is also not quite as likely that the students will write monster methods, though you need to guard against the SEE-ALL-DO-ALL class, just as you need to guard against the ONE-TRUE-FUNCTION in procedural programming.
The beauty of the OO paradigm for teaching is this. While any language defines a virtual layer in which to program, the objectives of the language designer were not pedagogical. When you define a higher level virtual world atop the language level, you, in fact can use pedagogical principles to construct it and provide a world in which the key concepts are easier to learn. If that world is also Turing Complete, all the better, but it is not essential - especially if you intend to use several smaller worlds rather than a single framework.
Note that a few additional paradigms have been omitted here - concurrent programming, in particular.
A paradigm is a way of thinking. Adopting a new paradigm may require a radical change in how the students think. This is much like the change in warfare from aristocratic knights on horseback to a peasant army of longbow archers that was first recognized at Agincourt in 1415. However the change did not become complete for about 100 years, Henry V to Henry VIII. After Henry VIII, English kings were no longer trained as knights.
Paradigms are by nature distinct. They are not ordered. A longbow-man did not need to have any of the knight's training to be successful. The computing paradigms are also distinct and self-consistent, not ordered. It is not necessary to learn one before any other. Nor is it necessary to mix them. In fact, the second paradigm learned is always difficult, as you already know how to do things, so the new structures seem superfluous to you. That is not a reason for not learning several, but it needs to be kept in mind to help explain the difficulties. The first course, however should be pretty pure to avoid confusing students.
It is a fundamental principle of modern computer languages that they define an internally consistent, Turing complete, view of programming that needs no appeal to lower level constructs to be understood. While it is true that such languages are in fact compiled to lower level constructs it is inherent in the concept that understanding does not flow from compilation, but the other way about. In fact, most of us (non-compiler-builders) would have a hard time understanding the intricacies of what really goes on in an optimizing compiler. The basics are easy to get, and the details are very complex. If you had to understand all of that to write a C program you would never know where to begin. You make assumptions, but they may be wildly wrong in light of modern systems with multi-level cache, co-processors, etc. That understanding is not needed if the language itself is complete and consistent.
Many languages are designed around a particular paradigm, sometimes just due to the time of creation. C is procedural. Java is Object-Oriented. Haskell is Functional. Some, however are multi-paradigm; C++, for example, is neither duck, nor dog.
