As to Randall's Island itself, which (with neighboring Ward's Island, now joined to it) lies in the East River between East Harlem, the South Bronx, and Astoria, Queens... Prior to the New Deal it housed institutions such as an ophanage, a poor house, a reform school, a potters field, a refuge for sick and/or destitute immigrants, a mental hospital, and a home for Civil War veterans. A massive amount of work was done to demolish these buildings, relocate people, landscape the island, and build ballfields, tennis courts, playgrounds, paths, and roads, plus ramps connecting to Queens, the Bronx, and Manhattan. See this Parks Department press release to get an idea of the scale of this project. The work was performed by the Triborough Bridge Authority and the Department of Parks. As noted here, the TBA was funded by the New Deal Public Works Administration (PWA), and as noted here the Parks Department was overwhelmingly staffed by federal relief workers during this period so any Parks Department project in the 1934-38 period qualifies also as a New Deal project.
Besides all that, there was the historic Randall's Island Stadium, which was built by the WPA in 1936.