I'd stay away from the s3 at this point in time. Samsung have stopped updates for it, so it's is going to be stuck on an older version of android (unless your boyfriend roots which is a different story). With the big new android update coming up soon, that is going to become a nuicence.
Like the others mentioned, you can get the N5 for just around $400, it's going to be a lot better than any phones around it's price. Same with the Xperia Z Utra if you want something bigger. Other than that I'll parrot in for the Moto G and Zenphone. The Z ultra and especially N5 blow these out of the water in terms of speed though. They're more similar to the flagship, high end 2014 phones (That's the S5 and 2014 HTC One).