It sounds like each Agent should contain a reference
to the Movement that it uses.  It seems likely that the
Movement methods will need access to some Agent-specific
state -- position, velocity, attitude, whatever -- which
suggests that you'll need one of two strategies:

   1) Store the necessary state in the Movement object,
      which means you'll need a dedicated Movement for
      each Agent.  But these "thousands of instances"
      are not wasted, since you'd have needed to store
      the Agent-specific state *somewhere* in any case.

   2) Store the state in the Agent, and give the Agent
      a reference to a Movement object that can be shared
      with other Agents.  This requires that the state
      be passed back and forth between the Agent and the
      Movement, which means either a standardized set of
      state variables or some kind of MovementState wrapper
      object for the variables a particular Movement cares
      about -- and in the latter case, (1) seems simpler.

    These approaches (and some others, most likely) can be
adapted and blended in lots of ways; the choice is not
strictly either/or.

[..]

[..]

in your case, you say you "don't want to put the code in the agent class."
the short answer is: composition.  whatever "all of the code" means,
that's your class.  Maybe that code goes in Movement, maybe you make a
third class.  I say, the more the merrier!

thus Agent will be composed of ClassX and Movement.  to add functionality
to the Agent class, just create ClassY.  when you look at the Agent class
it'll be easy on the eyes, hopefully, which is what you're after if i read
you right.  the flip side is that you have to peek in ClassX to get to the
nuts and bolts, but that's a blessing in disguise since you now have
greater flexability.  particularly were you to add additional packages,
any changes to the underlying code shouldn't have any ripple effect.

some general ideas surrounding inheritance and interfaces:
example and counter-example (not sure which is first), apologies to Head
First Java:
                       optical drive
                            /\
         read write drive         dvd drive
                            \/
                        dvd burner

the /\ forms a diamond shape, which head first java calls the "diamond of
    \/
death", which causes the following problem:

ReadWriteDrive and DVDplayer extend OpticalDrive.  Which one does
DVDburner extend?  at least that's their argument, as i recall, against
multiple inheritance.

once multiple inheritance is ruled out as an option, that leads to asking
"why bother with an interface?"  consider:

Mammal is abstract, Cat and Dog extend Mammal, hence inherits mammal
methods like giveBirth(), eat(), suckle(), etc.  PetCat and PetDog
implement the Pet interface, which requires that these two classes
implement methods like beg(), trick(), etc.  RoboDog isn't a Mammal, it
extends Robot perhaps, but it certainly can implement the Pet interface.

There's even an argument against using inheritance at all, composition may
be prefferable (Effective Java).  in any event, the reason to use an
interface is increased robusteness.  If down the road you try to remove
beg() from RoboDog or PetCat you'll get a compile error which beats a run
time error from something else which depended on the beg(), for instance.

Thufir Hawat