Pode não ser isso, mas sua descrição me lembra o anime seminal Neon Genesis Evangelion. Ou, mais provavelmente, Reconstrução de Evangelion, uma série de filmes (três até agora, com um quarto no inferno do desenvolvimento) que recontam a história original com algumas mudanças.
This movie began with a guy walking into an empty city with a photo of a girl with an arrow pointing towards her boobs
O protagonista, Shinji Ikari, passa a série vivendo com uma mulher chamada Misato, que tem um busto não insignificante. Ela lhe envia um cartão postal para que ele a reconheça.
Later in the movie he gets enrolled in this mech program
Shinji de fato "entra no robô", como diz o ditado.
to save the city from giant blue crystals the bleed red and were trying to destroy the city
Os antagonistas de Neon Genesis Evangelion são os anjos, entidades alienígenas bizarras que estão tentando destruir o planeta. Um deles, Ramiel, é um octaedro azul gigante que grita.
He later bonds with a girl who had a terrible back story
Isso poderia ser literalmente qualquer uma das meninas em Neon Genesis Evangelion. Praticamente todos eles têm terríveis histórias de fundo.