Pataki would have an early edge from the name recognition of being the governor of NY. Nothing huge, but an edge.
If the GOP money machine kicked in behind him he could also have a money edge.
Bayh would have the benefit of having been both a state executive and a federal senator. If he remembers how to talk like an executive he would have an advantage.
Bayh would have a very good chance of picking up IN while NY would be an outside shot for Pataki. Pataki would have to convince the people of NY that he is more in touch with them than Bayh. Pataki would probably need to resign in 2006 to have any chance. People tend to remember you more fondly if you go away for a bit.
Ohio would be a battleground where Bayh would have an edge. PA is a tossup, better campaign takes it. NJ would be interesting, probably still go Dem, but would give a scare. FL would still be seen as the big prize and Pataki would have an edge there (Former NYers there give him a massive name recognition edge.) MO is a true battleground in this race and could go either way.
A lot would come down to how the campaign went and the VP choices to keep the parties base. I said before centrist v. centrist races are very rare and very interesting. They go to whoever can get the base out without alienating the center.
Pataki would not win NY period. He has virtually no chance of beating Spitzer in 06 if he runs again. If Pataki is interested in running he should announce in early 06 & not seek re-election because running for Pres after getting your butt kicked in the governor's race won't look good. His approval is in the low to mid 40's right now.