Hmm, I would not agree with Sheridan.
You want to annex all your neighbors. Force-annex the first few in offensive wars. You can keep costs down some by using diplo-annexation for later ones if you want.
It is true that by eliminating all your neighbors, you will increase your tech costs somewhat. But these costs are monumentally huge anyway, so much that before you connect with Europeans you won't get past level 1 in anything anyway. So might as well just bank the income. After the level 1s, do not concentrate (contra Sheridan); instead spread research evenly among land, infra, and trade. (Naval is a lost cause.) Then, when you finally do get European contact, it is possible to drop both the whiteman penalty and the isolation one in the same month, causing your tech-costs to plunge. Then you get full value for the banked research. (Tom has discussed how to do this, and I will try to dig it up and wiki it for you.)
On exploring: the first priority once you get a conquistador is to find the path to the Aztecs. (To conquer them, natch.) You will also want to explore all of the American coast with the good colonies. (Don't bother with New England until later; usually just take it from the British.)
Finally, on religion: this is a matter of taste, but I usually don't change religion. If you get one of those events relatively early, then it is probably a good idea. And also, if you are small. But if you are having a great game, it is quite possible to have absorbed the tribes you can get to (22 provinces), plus colonizing the 9 unsettled provinces you know about initially, by the time the Europeans come. So you're already at 31 provinces... add on the Dakota and Navaho, and Central America, and some more colonies and you are already maxxing out the cities penalty. Once you get above 50 or so cities, changing religion still improves the religion modifier to tech cost, but that is all, and it dramatically raises your tech costs. It does, however, mean that the Euros won't DoW you all the time. So, depends a lot on what you want.