If had decided to run, he almost certainly would have won the primaries once Gary Hart blew himself up.
Early polling had him trailing only Hart, with the rest of the candidates way down in the polls (with the exception of a rapidly ruled out Teddy Kennedy run)—if I recall correctly, without sources in front of me.
For starters Cuomo was widely considered one of the best fund-raisers in the Democratic Party at the time: due to being based in New York, his 1984 "Two Americas" speech which cemented him as one of the two leading liberal lights of the Democratic Party, and of course his own personal talents.
So money, in the primaries, should not be a problem. Particularly compared to all non-Dukakis candidates (Dukakis himself relied heavily on Greek-American funding) that gives him a sizable edge. Secondly his close proximity to N.H. gives him many of the same advantages Dukakis had in that state.
Really, the primaries are not the problem.
The general election is a different matter. Possibly the most important point to make is that Cuomo attracts a lot of activist Democrats—including the top flight consultants. A vast percentage of the 1988 campaign staff picked their candidate as their second choice after Cuomo declined to run. That gives a wider talent pool than any other Democrat.
At the very minimum that should mean a far better and tougher response to Atwater on the Republican side. Furthermore Cuomo is from New York, one of the nastiest political climates in the nation—especially in the '70s when Cuomo was learning his political education (and losing the race for Mayor). We will see, if not overall as negative a campaign as the Republican one, one that matches it in many ways.
Being from New York and one of the last (if certainly one of the most eloquent) of the old pre-McGovern liberals he absolutely needs a fairly conservative VP pick, possibly from the West or industrial states but probably from the South.
I'd wager a Senator is more likely than a Governor, but it could easily go either way. Gore, actually, fits the bill in a lot of ways as does Bentsen. As Historico does in his President Bentsen scenario Governor Bob Casey of Pennsylvania is an outside-the-box choice do to his being pro-life which Cuomo himself struggled with being a Catholic (and, as Historico had, this may bring on Carville & Begala on as stratigists).
Perennial VP candidate Senator Sum Nunn of Georgia, Senator Dale Bumpers of Arkansas, and Senator Bob Graham of Florida should all be considered shortlist candidates as well.