I haven't heard Arrau's recording, but I'm sure it is superb. I would recommend Rubinstein's, for both concerti, and also it would be interesting to get Gould's. I actually love Gould's--indeed it was the first I heard--not to say I understand it entirely but I think it sounds good at that pace (which is, if you don't know, (in)famously slow, though to be honest in reality it isn't as slow as some reviewers might have you believe), as Gould--and Bernstein for that matter, though he was somewhat opposed to the performance--was able to bring out certain aspects about the music one might not normally hear. Actually, I felt a little disappointed at first when I heard a few other recordings, including Rubinstein's, because their tempi seemed so fast as to overlook some of the more exciting aspects of the piece.
Julius Katchen holds my favourite recording of both concerti, with Arrau and Gilels not far behind!