What is the correct way to implement the comparison for a base class?

One way to implement this, is to use double-dispatch to differentiate between 'same class' and 'different classes':

class Monkey;
class Snake;

class Animal {
public:
  virtual bool compare_impl(const Animal*) const { return false; }
  virtual bool compare_impl(const Monkey*) const { return false; }
  virtual bool compare_impl(const Snake*) const { return false; }
  virtual bool compare(const Animal* rhs) const =0;
};

class Monkey : public Animal {
private:
  /* Override the default behaviour for two Monkeys */
  virtual bool compare_impl(const Monkey*) const { /* compare two Monkey's */ }
public:
  /* Let overload-resolution pick the compare_impl for Monkey and let virtual dispatch select the override in the dynamic type of rhs */
  virtual bool compare(const Animal* rhs) const { return rhs->compare_impl(this); }
};

class Snake : public Animal {
private:
  /* Override the default behaviour for two Snakes */
  bool compare_impl(const Snake*) const { /* compare two Snakes */ }
public:
  /* Let overload-resolution pick the compare_impl for Monkey and let virtual dispatch select the override in the dynamic type of rhs */
  virtual bool compare(const Animal* rhs) const { return rhs->compare_impl(this); }
};

Wow, a lot of the other answers were so totally unnecessary. dynamic_cast- it exists, use it.

class Animal {
public:
    virtual bool operator==(const Animal& other) = 0;
    virtual ~Animal() = 0;
};
template<class T> class AnimalComp : public Animal {
public:
    virtual bool operator==(const Animal& ref) const {
        if (const T* self = dynamic_cast<const T*>(&ref)) {
            return ((T*)this)->operator==(*self);
        }
        return false;
    }
    virtual bool operator!=(const Animal& ref) const {
        if (const T* self = dynamic_cast<const T*>(&ref)) {
            return ((T*)this)->operator!=(*self);
        }
        return true;
    }
};
class Monkey : public AnimalComp<Monkey> {
public:
    virtual bool operator==(const Monkey& other) const {
        return false;
    }
    virtual bool operator!=(const Monkey& other) const {
        return false;
    }
};
class Snake : public AnimalComp<Snake> {
public:
    virtual bool operator==(const Snake& other) const {
        return false;
    }
    virtual bool operator!=(const Snake& other) const {
        return false;
    }
};

Edit: Bow before my automatic templated implementation!

Edit edit: One thing I did do was forget to tag them as const, which was wrong of me. I will not apologize for not doing != as, let's face it, implementing it is a total doddle.

More edits: this is not an example on how to write != or ==, it's an example of how to use the CRTP.

Since there is no static type information associated with the two pointers, you will need to use RTTI. You can compare the results of type typeid operator to determine if the objects are of the same type.

An alternative would be to add your own type ID to the Animal class. Add another virtual function and have derived classes return something that uniquely identifies the type. You could use an enumeration, or maybe the name of the type as a string. If you can use it, though, RTTI would be much better IMHO.