Dewey was in a terrific quartet in the 70's with Keith Jarrett,Paul Motian and Charlie Haden. Not a shabby group of players! They put out a bunch of records on Impulse though not many are on the market in CD form. I recommend Fort Yawuh for starters, or if you get a good deal on it, the Impulse collection.
Jarrett also recorded with his European Quartet with Jan Garbarek in the same time frame...another excellent group, though pretty different if you know how Garbarek's style differs from Redman's.
Besides Old and New Dreams self-titled disc, I believe there is another one out on Black Saint. I need to go thru my vinyl.