The agents we used were called Cannon Kaller and were fucking useless but they were taken over by Keaton’s during our tenancy who were a lot more competent. They’re based on Deptford High Street and “not useless” is about as high a bit of praise as I’ll give a letting agents frankly.
Reckon you should be able to get somewhere for £1000 a month or less in New Cross which, whilst obviously stupid money, is a hell of a lot more affordable than many other places that won’t be as convenient for both of you.