As for the result, Hendryk is right on. The only possible difference would be the effect of disease. It is possible that the native civilizations would undergo considerable stress, population loss and even partial collapse as a result of plagues. This might create local conflicts and collapses into which Europeans insinuate themselves much more quickly and thoroughly than in India and China.
I also tend to agree with Umbral that, for native american civilizations to have reached the level of technological development and political organization of the Roman Empire when Columbus arrives, there would probably have had to have been some trans-atlantic or trans-pacific contacts to allow the spread of eurasian animal husbandry, iron metalurgy, and possibly even some old world ideologies. This creates its own butterflies. It might minimize the impacts of disease in the 1500's. Perhaps there would be some dim knowledge that there was "a new world" in Europe or Asia, creating earlier voyages of exploration. Perhaps the new world civilizations, knowing that traders came from accross the sea from Phonecia, China, or wherever would themselves adopt maritime technologies and be the ones making the contact. An interesting speculation might be what the effect would be on Europe if some sword-wielding, horse riding Aztec "cortez" landed in Spain - even if he represented a civilization well-behind 1500's europe.