I've been very pleased with my Aquabot X4. Got it with the caddy and 3 year warranty for $600. Just above your limit but might be worth considering. It does a great job with my pool which is just a bit larger than yours.
No complaints at all. It does not climb walls regularly. Sometimes it does and it remembers that it's only a $500 cleaner and quickly comes back down before getting into trouble by Hayward. Seriously, I think the only difference between this model and one that climbs walls is in the software programming or power module.