Besides the 46-disk Brahms Edition (DG), there's numerous excellent Brahms recordings available on Spotify. An overview of the playlist:
Piano works: Sviatoslav Richter, Murray Perahia, Emil Gilels, Martha Argerich, Nicholas Angelich, Radu Lupu, Julius Katchen, Yuja Wang, Stephen Kovacevich, Clifford Curzon (Concerto No. 1), Claudio Arrau (Concerto No. 2), Olga Kern (her Variations is beautiful), and more. For the Haydn Variations, you can hear Solti and Perahia on two pianos.
Orchestral and choral works: Otto Klemperer (Walter's recording of Ein deutsches Requiem is also great but it's in mono; Klemperer's recording was made around the same time he recorded the legendary St. Matthew Passion, with the same artists), John Eliot Gardiner (new recordings on SDG), Leonard Bernstein, Simon Rattle, Carlos Kleiber, Bernard Haitink (new recordings with LSO), Claudio Abbado, Adrian Boult, Sir John Barbirolli, and more. It is worth noting that, the conductor of Serenade No.1, Robin Ticciati, was 27-year-old when he made the recording, the same age as when Brahms completed the piece.
Chamber music: too many to mention. The two clarinet sonata recordings from Harmonia Mundi and Delos are celestial. On Spotify's desktop app, you can use Ctrl + F to bring out the filter bar, and type in clarinet to find the recordings quickly.
Vocalists: Lorraine Hunt Lieberson, Dietrich Fischer-Dieskau, Jessye Norman, Elisabeth Schwarzkopf, Anne Sofie von Otter, Thomas Quasthoff, Ann Murray, Andreas Schmidt and more.
This playlist is compiled after this list of compositions. Besides all WoOs, I added a few works from the appendix (mostly arrangements of other composers' works; complete arrangements for piano-four hand will be available as another playlist), and
- Original 1853 version of Piano Trio op. 8
- Sinfonia in B, an orchestration of the above work
- Alternative ending for Schicksalslied, Op. 54
- Piano Trio No.4
- Souvenir de la Russie (published before 1852 as op.151 under the pseudonym G.W. Marks)
Also check out Naxos Educationa for a 4-disk audiobook on Brahms's Life & Works and 2-disk analysis of his 2nd Piano Concerto.