Si, en el alquiler en Madrid suelen pedir autenticas burradas, sobretodo el aval bancario que si dos fianzas me parece una ridiculez, el aval ya no te cuento. Mira en webs intenta particulares pero si no te queda otra, inmobiliaria, pero te van a intentar sacar un mes de comisión ademas de las fianzas.
Sobre la zona, mira a cuento esta tu trabajo de la estación de tren de Majadahonda, ya que yo te recomiendo que te muevas en cercanías por Madrid. Píllate el bono mensual solo de tren que te sale mas barato que el bono transporte y con eso puedes hacer 4 viajes al día, si no recuerdo mal. Teniendo la opción del tren puedes mirar zonas para vivir mas alejadas de tu lugar de trabajo, porque es el medio de transporte mas rápido.
Sobre barrios en concreto no te puedo ayudar, pero en general la mayoría de zonas de Madrid son buenas, lo que influye es el precio y el nivel de la zona.
Mi consejo es que compartas piso al principio, o mejor aun, mires un hostal, hotel o apartamento donde alquilen por meses, pudiendo estar ahí 2 o 3 meses te da tiempo a mirar zonas, barrios y pisos con tranquilidad.