How to START an Objects-First Course
I'll try not to write a book as an answer here, but my experience with this is long and deep. 

The first thing you need to know is that you don't start with just the programming language itself. If you try to teach integer variables and 'if' and 'while' statements before you get to objects you may fail. I'm going to assume that your intention is to teach a first course that is also objects first. The students in a course like that might have no prior computing experience, though some will have. 

The key to a successful course is to teach object-oriented problem solving, and not an object oriented language. In fact teaching problem solving via programming should be the objective of any first course no matter the paradigm. You want the students to learn to use objects and you want them to learn to create objects and you want them to be able to define new kinds of objects. But you don't need to do those all at once. You can spread it out over a short period of time - days, not weeks. 

The key is proper scaffolding, written (or found) by you. The students work within a defined framework that can be quite complete (even Turing Complete). Another big idea that you want to believe yourself and teach your students is that an object is a "bundle of behavior."  Never mind instance variables (fields) at the beginning and never mind getters and setters. Define for the students one or more kinds of objects and their behaviors. I've done this with most OO languages and all of them can be introduced the same way. I'll focus on Java for the rest of this, as it is the language of APCSA. It is also a good, though not perfect, OO language widely used in industry. 

I have a lot of experience with Karel J Robot (KJR) so let me describe how it can be used as an introduction, that might take half of the first course in computing and teach students how to program. It is not, however, specifically tied to APCSA, nor does it cover every topic needed by your students. But in about half the first course, students will be able to write serious programs that require deep thought. At the end, I'll try to list many of the things not covered. 

The KJR world is a simulation in which one or more robots can be created and which have a few behaviors. The "world" of the robots is a rectangular grid and one or more robots can occupy an intersection. An intersection can also contain one or more movable "beepers" that robots might pick up or put down. Infinitely many beepers (effectively a beeper making machine) is also possible at an intersection. A robot always faces in one of the cardinal directions North, South, East, or West. A robot can perform one of five primitive actions: move, turnLeft, pickBeeper, putBeeper, and turnOff. Those are your primitive behaviors and when the student begins programming, nothing else is known, though some additional things are revealed later in the course. In particular, a robot doesn't "know" where it is in the world. The world can also contain walls between intersections that will block forward movement and cause an error if a robot attempts to move through them. 

So, what kinds of programs can you write (using only main and the primitives? Well, to a programmer they are pretty boring: Move forward three blocks, pick up the beeper that is there and return to the initial position and direction. The solution is just a sequence of primitive actions, of course: move(); move();...

Students see a bit of syntax in the language and think in terms of the behaviors and nothing else. The learn about statement sequences, the most primitive control structure of  programming (arguable, I guess). 

Next they get a much more complex problem (first day's homework), which if solved with only sequences of primitives is unwieldy. It is obvious that something better must exist. But if you choose that program correctly you can notice that there are patterns in the solution. Even in the first assignment the robot had to turn around twice and had to move three blocks twice. 

On the second day you discuss the homework and find the repeated sequences of instructions. Now you introduce a new class (their first view of a class) in which you get newly defined behaviors. This class is a subclass of the most primitive class. You are introducing inheritance (too early perhaps, but essential in KJR). The new class has a few additional methods: turnAround(), moveMile()... Note that it is too early to introduce parameters. All of the methods so far, and for a long way in KJR, are mutators, the state of the robot is changed in some way. But the notion of a mutator is in no way linked to any idea of a "setter." 

Now you have the basic framework of problem solving. Define a new class. Within it define new behaviors. Create robots with new... and exercise the new behaviors to satisfy some programming task. 

Note what is NOT done. There is never any speculative class writing. All classes are purpose built to solve some small part of a larger problem. The book talks about the decomposition process in detail. 

You are now in the third day of class and have covered three chapters of the book. The fourth chapter is much deeper and discusses polymorphism, largely by showing how the Strategy design pattern can be used to modify the behavior of a given robot without writing a new robot class. Instead Strategy classes (and Decorators) are used to build a much more sophisticated model of computing. This chapter requires several days. It introduces object-valued variables which up to now have only referred to robots. 

The fifth chapter introduces selection and there the student learns about booleans as well as the fact that robots also have some self knowledge. However, there are no methods returning information about the current location or explicit direction. A robot can respond true or false whether its front is clear (no wall) or if it is facing North, or if there is a beeper on the current intersection, etc. All of these accessor methods return booleans, so the student can now write conditional statements, which opens the door to more sophisticated exercises. These accessors are not "getters" either in concept or in fact. 

The sixth chapter is repetition, but note that the student already has a good knowledge of the nature of computer programming and they haven't seen any of the primitive data of Java other than boolean. For loops are introduced here, so integers are used, but only in simple ways - step counting, for example. 

Later chapters (they are all pretty short) cover recursion and even concurrency. 

The key to all of this, however, was a well thought out scaffolding structure in which the students can learn deep lessons in a way that you can control and in which it is harder to go astray in the minute details that you find with integer operators, float/double, ... The point isn't to teach Java as a language, but how to think like a programmer - specifically as an OO programmer. 

The BIG idea

Java defines a logically consistent virtual world in which students can program without reference to lower level (machine level constructs) and can create consistent mental models without having to mentally compile their code to bits. A well designed simulation defines a yet higher level virtual world that if (Turing) complete can be used without reference to lower level constructs to solve any problem. That is very powerful. Robots can sort (piles of beepers) for example. 

A slightly smaller idea is that you, the instructor, should think about what not to teach, especially at the beginning, as you do about what to teach. Teaching a complete subset intensely can be more powerful than teaching "the whole enchilada" at a shallower level. 

Caveats

If the instructor skips the polymorphism chapter, students will come away with the unfortunate view that OO programming is all about inheritance as all of the robot classes must derive from a simpler such class. In fact, OO is really all about building "bespoke" or "tailor made" objects out of parts that are also objects. Skipping polymorphism also gives the impression that selection and repetition are all you need in order to know "how to program", that they are the real thing, an impoverished view IMO. 

KRJ is not the only way that you can implement this general course framework. The Greenfoot system is a simulation rich world in which you can build similar (or not so similar) things and use the same general plan. There is an associated instructor site, the Greenroom, to which teachers have contributed many simulations. The general idea there is a World in which Actors can move, turn, interact, etc. 

What is missing

The big one is counting with integer variables (other than simple for loops). One issue with teaching int and counting early is that from then on every problem becomes a counting problem, so students wind up with a poor mental tool kit. If you teach counting later, rather than earlier, students need to think harder about problems. You can "count" with decorators and encapsulate the actions themselves, rather than just the count in a (strategy) variable. You also can teach recursion without having to justify it as an alternative to counting. 

There is no discussion in KJR of many of the things we love, arrays, for example, collections, iterators, and such. There is a companion book that covers most of what would normally appear in a first course but it assumes the students can already write sophisticated programs. 

APCSA

In the past Karel was used a lot by AP teachers, but the course has changed as has the exam. I've never tried to use it to teach APCSA. I'm sure there are many things missing that the instructor would need to add to a complete course.