[1][5] Upon release after two years, Costa again worked around the New York area, including for bands led by Kai Winding, Johnny Smith, and Don Elliott.
The following year, Costa recorded a series of piano duets with John Mehegan; differences in playing style meant that several rehearsals were required to organize which pianist would be responsible for what aspects of the performances.
[11][12] Also in 1956, Costa and Burke joined guitarist Tal Farlow, forming a resident trio to play at the Composer, a club on West 58th Street in New York.
[13] Farlow's comment on the absence of a drummer from the trio was that "Eddie's feeding, comping or whatever you want to call it was so fierce that there was no doubt at all where the time was, so I didn't miss the drums at all".
These included small group settings with Herbie Mann, Oscar Pettiford, and Phil Woods, and accompanying vocalists such as Tony Bennett and Chris Connor.
Their repertoire featured interpretations of "I Didn't Know What Time It Was" and Dave Brubeck's recent composition "In Your Own Sweet Way"; the latter focused on Costa's vibes and Farmer's muted trumpet, with Woods switching from his usual alto saxophone to the piano.
Some of his playing at the festival – as a trio with Ernie Furtado (bass) and Al Beldini (drums), and as a quintet with the addition of Rolf Kühn and Dick Johnson – was released later in 1957 as part of a Verve album.
Costa's final recording session was on July 12, 1962, as part of a group assembled by saxophonist Al Cohn mainly from the Benny Goodman band that had toured the Soviet Union earlier that year.
[27] His piano playing on the informally recorded album Fuerst Set is typical of his style; it was later described by critic Whitney Balliett: Each improvisation resembled an excellent drum solo in its rhythmic intensity, pattern of beats, and elements of surprise.
He would let loose a staccato passage and then an impossible two-handed arpeggio, or he would deliver on-the-beat or offbeat chords – seesawing them, making them into sixty-fourth notes, somehow slurring them, and developing great drive and momentum.
John S. Wilson commented in 1959 that "In contrast to the stirring forays into the lower register that he is fond of making on piano, Costa's vibraphone style is light and dancing, closer to the Red Norvo manner than most current vibists.
"[10]: 75 After Costa's death, Alun Morgan also compared his playing on the two instruments: "As a vibraphonist Eddie carried over the pulsating elements of his piano style but also continued to employ a sensitive gradation of touch where necessary".
[30] An indication of the esteem in which Costa was held by musicians is the caliber of those who performed at his memorial concert at The Village Gate on October 8, 1962: Charlie Byrd, Al Cohn, Art Farmer, Benny Golson, Jim Hall, Coleman Hawkins, Mundell Lowe, Zoot Sims and Clark Terry were among those who played.